046 · Single Number
My First Thoughts
嗯，这道题刚看到会想到前面的 Majority Element，因为它好像也是一个“抵消”的问题。
Majority Element 里可以维护一个候选值和一个计数器。因为多数元素超过一半，所以不同元素互相抵消以后，多数元素还能剩下来。
这题也有类似的味道：所有数字都成对出现，只有一个数字不是成对的。
最直接的粗暴方法是先遍历一遍，计算每个数字出现的次数。然后再遍历 counts.items()，找到次数等于 1 的那个数字：
def singleNumber(nums):
counts = {}
for num in nums:
counts[num] = counts.get(num, 0) + 1
for key, value in counts.items():
if value == 1:
return key这个写法是对的。它把问题翻译成了：
谁出现了一次，就返回谁。
然后还能想到一个更贴近“抵消”的做法：用一个 set。
遍历数组时：
- 如果当前数字不在
set里，就把它加入 - 如果当前数字已经在
set里，说明这是第二次遇到它，就把它移除
代码大概是：
def singleNumber(nums):
seen = set()
for num in nums:
if num in seen:
seen.remove(num)
else:
seen.add(num)
return seen.pop()这个也能工作。因为出现两次的数字会经历：
第一次遇到 -> 加入 set
第二次遇到 -> 从 set 移除最后 set 里只会剩下那个出现一次的数字。
到这里其实已经抓住了这题最关键的结构：
相同的数字应该互相抵消。
只是还有一个问题：这里是整数。既然所有数都成对出现，只有一个不是，那么整数本身有没有什么运算可以天然表达这种“抵消”？
如果不知道这个运算符，就很难继续想到最优解。
Why That Is Not Enough
哈希计数和 set 抵消都是正确解法。
它们的问题不是逻辑错，而是都需要额外空间：
- 哈希计数要记录每个数字出现了几次
set要保存当前还没有被抵消掉的数字
这题还能继续优化，是因为它有一个非常强的条件：
除了一个数字以外，其他数字都恰好出现两次。
如果有一个运算能做到：
x 和 x 运算 -> 0
x 和 0 运算 -> x
运算顺序不影响结果那就不需要 counts，也不需要 set。只要把所有数字一路运算过去，成对出现的数字会自动变成 0，最后只剩那个单独的数字。
这个运算就是 XOR，也叫“异或”。在 Python 里写作：
^Final Idea
XOR 是一个按位运算。它比较两个整数的二进制位：
两个 bit 相同 -> 0
两个 bit 不同 -> 1也就是：
0 ^ 0 = 0
1 ^ 1 = 0
0 ^ 1 = 1
1 ^ 0 = 1所以它有两个特别适合这题的性质：
x ^ x = 0
x ^ 0 = x比如 5 ^ 5：
5 = 101
5 = 101
-------
000所以相同数字可以被 XOR 抵消掉。
再看题目的例子：
nums = [4, 1, 2, 1, 2]如果把所有数字都 XOR 起来：
4 ^ 1 ^ 2 ^ 1 ^ 2因为 XOR 的顺序不影响结果，可以理解成：
4 ^ (1 ^ 1) ^ (2 ^ 2)成对的数字抵消成 0：
4 ^ 0 ^ 0最后剩下：
4所以我们只需要维护一个变量 result。一开始设成 0，然后遍历数组，每次把当前数字 XOR 进去：
result = result ^ num遍历结束后，result 就是只出现一次的数字。
Why It Works
题目保证除了一个数字以外，其他数字都出现两次。
对于任何出现两次的数字 x，在整体 XOR 结果里都会有：
x ^ x = 0所以这些成对数字都会被抵消掉。
对于那个只出现一次的数字 single，它没有另一个相同数字可以抵消。
当所有成对数字都变成 0 以后，整体结果就等价于：
0 ^ 0 ^ ... ^ single而：
0 ^ single = single所以最后返回的就是只出现一次的数字。
Code
def singleNumber(nums):
result = 0
for num in nums:
result = result ^ num
return result也可以写成更短的形式：
def singleNumber(nums):
result = 0
for num in nums:
result ^= num
return result这里的：
result ^= num等价于：
result = result ^ numComplexity
| Time | \(O(n)\) - 只遍历数组一次 |
| Space | \(O(1)\) - 只使用一个 result 变量 |
Takeaway
当题目里出现“其他元素都成对出现，只有一个元素落单”时，可以先想到哈希计数或
set抵消；如果元素是整数，再进一步想 XOR。x ^ x = 0正好表达“相同元素抵消”，x ^ 0 = x正好保留最后落单的元素。
← Quiz