力扣133题：只出现一次的数字

力扣133题：只出现一次的数字

题目描述

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

说明：

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

其表明时间复杂度要为O(n)，空间复杂度为O(1)

输入输出样例

输入: [2,2,1]
输出: 1
1
2

输入: [4,1,2,1,2]
输出: 4
1
2

算法一：使用hash进行求解，空间复杂度不存在

 //使用hash进行求解
        int singleNumber(vector<int>&nums)
        {
            unordered_map<int ,int>umap;
            for(auto x:nums)
            {
                if(umap.count(x))
                {
                    umap[x]=2;
                }
                else
                {
                    umap[x]=1;
                }
            }
            for(auto num:umap)
            {
                if(num.second==1)
                {
                    return num.first;
                }
            }
            return NULL;
        }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

解法二，使用vector的count操作，时间复杂度不满足

//使用vector容器自带的count，时间复杂度不满足
    int singleNumber2(vector<int>& nums) {
        int i=0;
        while(1)
        {
            int num=count(nums.begin(),nums.end(),nums[i]);
            if(num==1)
            return nums[i];
            i++;
        }
    }
1
2
3
4
5
6
7
8
9
10
11

解法三，使用位运算的方式

    //使用位运算的方法,使用异或的方法，异或相同为0，不同为1，可满足交换律和结合律
    int singleNumber3(vector<int>& nums) 
    {
        int xores=0;

        for(auto nums:nums)
        {
            xores^=nums;
        }
        return xores;
    }
1
2
3
4
5
6
7
8
9
10
11