寻找只出现一次的数

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int res = nums[0];
        for (int i = 1; i < nums.size(); i++)
        {
            res = nums[i] ^ res;
        }
        return res;
    }
};

根据异或的特性可知，a ^ a = 0。即任何数与其本身异或的结果为0。而0 ^ b = b，即任何数和0进行异或得到它本身。那么，在数组中其它数字都是成双出现时，由于异或满足交换律。只要将数组中每一个数都相互异或，那么成双出现的数就会异或为0，而出现次数为奇数的则会留下来。例如：a ^ b ^ c ^ d ^ b ^ d ^ c 等价于 a ^ b ^ b ^ c ^ c ^ d ^ d = a ^ 0 ^ 0 ^ 0 = a。

同理运用这个规律，我们不仅可以用于寻找只出现一次的数，还可以反过来，在数组取值范围为 [1, n]时，如果给定n + 1个数，在只有一个数字重复的情况下，求出唯一一个重复的数。

时间复杂度：

O(n)

空间复杂度：

O(1)