136.只出现一次的数字

异或

这个真的想不到，只能想到用额外空间的哈希表或不用额外空间但O(n)的排序

• 异或运算有以下三个性质。

1.任何数和 0 做异或运算，结果仍然是原来的数，即 a \oplus 0=a。
2.任何数和其自身做异或运算，结果是 0，即 a \oplus a=0。
3.异或运算满足交换律和结合律，即 a \oplus b \oplus a=b \oplus a \oplus a=b \oplus (a \oplus a)=b \oplus0=b。

假设数组中有 2m+1 个数，其中有 m 个数各出现两次，一个数出现一次。令 a_{1}、a_{2}、\ldots、a_{m}为出现两次的 m 个数，a_{m+1}为出现一次的数。根据性质 3，数组中的全部元素的异或运算结果总是可以写成如下形式：

(a_{1} \oplus a_{1}) \oplus (a_{2} \oplus a_{2}) \oplus \cdots \oplus (a_{m} \oplus a_{m}) \oplus a_{m+1}

根据性质 2 和性质 1，上式可化简和计算得到如下结果：

0 \oplus 0 \oplus \cdots \oplus 0 \oplus a_{m+1}=a_{m+1}

因此，数组中的全部元素的异或运算结果即为数组中只出现一次的数字。

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ret = 0;
        for (auto e: nums) ret ^= e;
        return ret;
    }
};

350.

本作品采用《CC 协议》，转载必须注明作者和本文链接