异或的妙用

本来觉得这题很简单的。但看了条件之后发现还真挺难想（压根想不到位操作）

原题链接

注意条件!!

线性时间 & 常量额外空间

思考

1. 暴力解法。

取一个数记为 cur ，然后从剩下的数中查找，如果找不到，则 cur 即为要找的那个数。

双层循环，时间复杂度O(n^2)。

不满足线性时间。

2. 哈希表

直接用unordered_set<int, int>作哈希表。

第一次遇到这个数时放进去，同时记录个数。

最后循环一遍看谁的个数是1。

然而这个解法不满足常量额外空间。

3. 排序

排序完之后看谁的值只出现一次。

使用快速排序时间复杂度O(nlogn)，还是不够快。

4. 异或

重量级登场

首先了解什么是异或。

异或运算符在C++里是^。

两个输入相同时为0，不同则为1。

我们只需要使用它这几个性质。

• 任何数和 0 做异或运算，结果仍然是原来的数，即 a ⊕ 0 = a。
• 任何数和其自身做异或运算，结果是 0，即 a ⊕ a = 0。
• 满足交换律和结合律 （也就是说无论一对相同的ta相隔天涯海角，中途经历了多少事情，异或都能让它们匹配在一起为0）

(a1⊕a1)⊕(a2⊕a2)⊕⋯⊕(an⊕an)⊕am+1最后结果是
0⊕0⊕⋯⊕0⊕am+1=am+1

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14

class Solution
{
public:
    int singleNumber(vector<int> &nums)
    {
        int len = nums.size();
        if (len == 1)              //只有一个数就直接返回咯
            return nums[0];
        int ans = 0;               //第一个条件:任何数和 0 做异或运算，结果仍然是原来的数
        for (int num : nums)
            ans = ans ^ num;
        return ans;
    }
};