LeetCode 136. 只出现一次的数字
题目描述
题意分析
一个非空整数数组中，恰好有一个元素出现一次，其他每种元素都出现两次，需要返回这个只出现一次的值。重复元素不一定相邻，数组也不保证有序，元素可以是零或负数。
题目要求线性时间和常数额外空间。哈希表统计次数会占用额外线性空间，先排序再寻找则需要额外排序时间；应利用“其他元素成对出现”这个条件直接消去重复值。
解法：异或抵消重复元素
核心思路
[!blue]
异或
^按二进制位运算：同一位相同得到0，不同得到1。因此，一个数与自身异或会让每一位都变成零，即x ^ x = 0；一个数与零异或不改变任何位，即x ^ 0 = x。异或还满足交换律和结合律。把数组所有元素依次异或后，可以在推理中把相同值放到一起，让它们两两抵消；实际计算无需调整顺序，也无需真的排序。所有出现两次的数都抵消为零后，只剩下那个出现一次的数。
用
ans = 0开始累积。每处理一个元素，执行ans ^= num，此时ans就是已处理前缀的异或值；遍历结束后，它就是整份数组抵消重复元素后的结果。负数同样具有确定的二进制表示，相同负数的每一位也会抵消，因此不用取绝对值或单独处理符号。
解题步骤
- 初始化
ans = 0，使第一个元素与它异或后保持原值。- 遍历数组，将每个元素恰好异或进
ans一次。- 返回
ans；所有成对元素已经抵消，结果就是唯一出现一次的值。
代码实现
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
}
复杂度分析
设数组长度为 $n$。
- 时间复杂度：$O(n)$，每个元素执行一次固定整数位宽的异或运算。
- 空间复杂度：$O(1)$，只维护一个累积变量，不修改输入数组。
关键点总结
[!green]
- 成对出现的相同数异或为零，零不会改变其余数的异或结果。
- 交换律和结合律使抵消过程不依赖元素相邻或数组有序。
- 这个结论直接依赖“恰好一个单次元素、其他元素成对出现”的条件。
易错点总结
[!yellow]
- 若把
ans初始化为nums[0]，遍历就必须从下标1开始；否则首元素会被重复异或，破坏出现次数。- 不要先取绝对值，异或本身支持负数，取绝对值反而会改变题目中的值及重复关系。
- 答案可能为
0，不能因为累积结果为零就认为没找到目标。- 如果其他元素出现三次，或有多个元素只出现一次，全部异或就不再能直接得到题目所需的单个答案。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 137. 只出现一次的数字 II | 中等 | 原题其他数出现三次，普通异或无法抵消，需按位模3或有限状态处理。 |
| 260. 只出现一次的数字 III | 中等 | 原题有两个只出现一次的数，需先用异或结果的某一不同位把它们分到两组。 |
| 268. 丢失的数字 | 简单 | 维护异或抵消关系定位少数异常值；本题其他值成对抵消后留下唯一值，该题将下标与数值异或以找缺失值。 |
| 389. 找不同 | 简单 | 维护异或抵消关系定位少数异常值；本题其他值成对抵消后留下唯一值，该题异或两个字符串以找新增字符。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！