LeetCode 136. 只出现一次的数字
目录
题目描述
题意分析
数组中除某个元素只出现一次以外，其余每个元素均出现两次，要求找出那个只出现一次的元素并返回。
约束信号很硬：题目要求线性时间复杂度，且只使用常数级额外空间。这两条合在一起，直接排除了「哈希表计数」（空间 $O(n)$）和「先排序再找落单」（时间 $O(n \log n)$）这两条最顺手的路。
边界上注意：数组至少含一个元素，单元素数组直接返回它本身；元素可以为负数；答案保证存在且唯一。
解法：异或抵消重复元素
核心思路
问题关键：题目同时要求 $O(n)$ 时间和 $O(1)$ 额外空间，因此排序的 $O(n \log n)$ 和哈希表的 $O(n)$ 空间都不满足要求。我们只需消掉成对元素，不需要保存每个元素的次数。
为什么选异或：异或满足
a ^ a = 0、a ^ 0 = a，并且具有交换律和结合律。把数组全部异或后，所有出现两次的数都能两两抵消，最终只剩出现一次的数。不变量与正确性：遍历过程中，
ans始终等于已处理前缀所有元素的异或结果。遍历结束后，可借助交换律将相同元素放在一起，每一对都变为 0，因此ans = 0 ^ single = single。负数使用补码参与按位异或，不需要特殊处理。
解题步骤
- 初始化
ans = 0，因为 0 是异或运算的单位元。- 遍历数组，执行
ans ^= num。- 返回
ans。例如[4,1,2,1,2]可重排理解为4 ^ (1 ^ 1) ^ (2 ^ 2)，结果为 4。
代码实现
class Solution {
public int singleNumber(int[] nums) {
int ans = 0;
for (int num : nums) {
ans ^= num;
}
return ans;
}
}
func singleNumber(nums []int) int {
ans := 0
for _, num := range nums {
ans ^= num
}
return ans
}
复杂度分析
- 时间复杂度：$O(n)$，每个元素只参与一次异或。
- 空间复杂度：$O(1)$，只使用一个累积变量。
关键点总结
- “其余元素恰好出现两次”是异或能直接抵消的前提。
- 交换律和结合律保证重复元素无需相邻，也无需排序。
- 若其余元素出现三次，要改用逐位计数模 3；若有两个落单元素，要先异或再按不同位分组。
易错点总结
ans = nums[0]后仍从下标 0 遍历：首元素会被异或两次；[4,1,2,1,2]将错误返回 0。- 先取绝对值：
[-1,2,2]应返回-1，补码异或本来就支持负数。- 照搬到其余元素出现三次的题目：
[2,2,3,2]全部异或得到 1，不是 3。- 使用哈希表或排序：结果可以正确，但分别违反 $O(1)$ 空间或 $O(n)$ 时间要求，面试中不算最优解。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 137. 只出现一次的数字 II | 中等 | 其余元素出现三次，异或失效，改为逐位求和后模 3 |
| 260. 只出现一次的数字 III | 中等 | 两个数各只出现一次，按最低置位分组后各自异或 |
| LCR 004. 只出现一次的数字 II | 中等 | 与 137 同型，检验位计数写法的熟练度 |
| 剑指 Offer 56 - I. 数组中数字出现的次数 | 中等 | 与 260 同型，重点在「选哪一位分组」的推导 |
| 剑指 Offer 56 - II. 数组中数字出现的次数 II | 中等 | 与 137 同型，可推广为「其余元素出现 m 次」的位统计 |