只出现一次的数字
Single Number
数组中只有一个元素出现一次，其余元素都出现两次，找出这个只出现一次的元素。
在力扣中练习题目描述
给你一个 非空 整数数组 nums ，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
你必须设计并实现线性时间复杂度的算法来解决此问题，且该算法只使用常量额外空间。
示例 1 ：
输入：nums = [2,2,1]
输出：1
示例 2 ：
输入：nums = [4,1,2,1,2]
输出：4
示例 3 ：
输入：nums = [1]
输出：1
提示：
1 <= nums.length <= 3 * 104-3 * 104 <= nums[i] <= 3 * 104- 除了某个元素只出现一次以外，其余每个元素均出现两次。
解题思路
主解法
位运算 · 全体异或
相同的数异或为 0，剩下的就是那个单数
最直接的做法是用哈希表计数，或者排序后找落单的元素，但都需要额外空间或 O(n log n) 时间。
异或有三个性质：
a ⊕ a = 0
a ⊕ 0 = a
a ⊕ b = b ⊕ a （交换律、结合律）
把数组里所有数异或起来，出现两次的数会两两抵消成 0，最后只剩那个出现一次的数。自拟主例 [9,4,7,4,9]：
0 ⊕ 9 = 9
9 ⊕ 4 = 13
13 ⊕ 7 = 10
10 ⊕ 4 = 14
14 ⊕ 9 = 7
分步图解
result = 0 ⊕ 9 = 9。
- x
- 9
- result
- 9
中间结果没有意义，但成对的数最终一定会抵消；顺序也不影响结果。
分步图解
result = 10 ⊕ 4 = 14。
- x
- 4
- result
- 14
时间 O(n)，只用一个变量，空间 O(1)。
时间 O(n)空间 O(1)
易错点
- 用加法或减法：只有异或才满足 a ⊕ a = 0，加减无法让成对的数抵消。
- result 初始化为 nums[0] 后又把 nums[0] 异或一次：第一个数被算了两次。
- 把异或当成“只适用于正数”：补码表示下负数同样满足这些性质。
对照解法
哈希集合 · 成对删除
第一次出现放进集合，第二次出现就删掉
时间同为 O(n)（期望），但需要 O(n) 额外空间；优点是逻辑直白，也容易扩展到“其他数出现奇数次”的变体。
用一个集合记录“目前只出现一次”的数：
- 遇到没见过的数：插入集合；
- 遇到已经在集合里的数：说明它出现了第二次，删除。
遍历结束后，集合里只剩那个单数。每个元素最多插入、删除一次，期望时间 O(n)，空间 O(n)。
它和异或版本解决同一个问题，但哈希集合不依赖“其他数恰好出现两次”这一位运算性质，读起来更通用；代价是额外内存。
- 1建立空集合 once。
- 2遍历 x：插入成功说明第一次见；插入失败说明第二次，删除。
- 3返回集合中剩下的元素。
时间 O(n)空间 O(n)
易错点
- 插入失败后忘记删除：集合里会残留成对的数。
- 集合最后可能为空：题目保证有且只有一个单数，但空输入需要额外处理。
代码与演示
主解法配有图解；对照解法用于比较思路、复杂度或实现方式。
演示输入
nums = [9,4,7,4,9]result = 0；异或满足 a ⊕ a = 0、a ⊕ 0 = a，而且顺序可以交换。
- result
- 0
查看 C++ 代码
延伸阅读
- 如果其他数出现三次，异或会失效，需要按二进制位统计模 3 的余数。
- 如果有两个数各出现一次，可以先用全体异或得到 a⊕b，再按最低不同位分组。