只出现一次的数字

问题拆解

数组里除了一个元素只出现一次，其余每个都恰好出现两次，要找出那个落单的数，并且要求线性时间、最好不用额外空间。

哈希表当然能做：扫一遍记录每个数出现的次数，再找次数为 1 的那个。但那需要 O(n) 的空间。题目里“每个数恰好出现两次”是个很特别的结构，值得找一种能让重复元素自动消失的运算。

异或有两条性质：x ^ x == 0，x ^ 0 == x。成对的数字异或后归零，只剩下那个单独的数。

异或消对

异或满足交换律和结合律，所以把所有元素异或到一起时，可以随意重新分组。出现两次的元素两两配对变成 0，最后与那个唯一元素异或，结果就是它本身。

def singleNumber(nums):
    result = 0
    for x in nums:
        result ^= x
    return result

以 [4, 1, 2, 1, 2] 为例，按位异或和与顺序无关，可以想象成 (1 ^ 1) ^ (2 ^ 2) ^ 4，前两组各自归零，剩下 4。初始值取 0 是因为它是异或的单位元，不会污染结果。

这里完全没有比较、没有计数，靠的就是位运算本身的代数性质，因此空间是常数。

复杂度

指标	复杂度	原因
时间	O(n)	每个元素参与一次异或
空间	O(1)	只维护一个累积结果

可以迁移的模式

• 元素成对出现，要找出唯一的“奇数个”那位；
• 允许用可交换、可结合、且自反（x ^ x == 0）的运算做累积；
• 想把空间从哈希计数的 O(n) 降到常数。

顺着这条思路，“其余元素各出现三次”可以逐位统计并对 3 取模，“恰好两个只出现一次的数”则先整体异或再按某一位拆成两组分别处理。