算法现学现卖—— 有趣的位运算（一）

有趣的位运算 —— 异或排除重复的元素

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

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

  示例1：
  输入: [2,2,1]
  输出: 1

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

该题想让我们找出数组里的唯一元素，直觉上我们会使用哈希表，将重复的元素记录下来判断，但哈希表会占用额外的内存空间，如：

class Solution:
    def singleNumber(self, nums: List[int]) -> int:
        h = defaultdict(int)
        res = 0
        for n in nums:
            h[n] += 1
            if h[n] > 1:
                res -= n
            else:
                res += n
        return res

如果用位运算异或，将重复元素排除，即可找出不重复的元素了，用异或的原因是：

1. 任何数与0异或得到自身；
2. 任何数与自身异或得到0；
3. 异或满足结合律；

则最终实现如下：

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

这时候是常量级别的空间复杂度。