leetcode-136. 只出现一次的数字

136. 只出现一次的数字

题目要求找出数组中只出现一次的数字。我首先想到用哈希表统计每个值的出现次数，再找出次数为 1 的那个值：

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        hs=dict()
        for i in nums:
            hs[i]=hs.get(i,0)+1
        for key in hs.keys():
            if hs[key]==1:
                return key

这里虽然写了两个 for 循环，但它们依次执行，并非嵌套，所以时间复杂度仍为 O(n)。不过哈希表需要 O(n) 的额外空间，不满足题目要求的常数空间。

要减少额外空间，可以使用异或运算。它逐位比较两个数：对应位不同，结果为 1；相同，结果为 0。下面几个性质正好适合这道题：

一个数与 0 异或，结果还是它本身，即 x^0=x。例如 9 的二进制为 1001，每一位与 0 异或后都不变，结果仍为 1001。
两个相同的数异或，结果为 0，即 x^x=0。例如 1001 与 1001 的各位都相同，异或后得到 0000。
异或满足交换律和结合律，因此 x^y^x=x^x^y，可以把相同的数放在一起抵消。

把数组中的所有数依次异或，成对出现的数字会抵消为 0，最后剩下的就是只出现一次的数字。整个过程只需一次遍历，时间复杂度为 O(n)，额外空间为 O(1)。

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        res=0
        for i in nums:
            res=res^i
        return res