LeetCode 剑指 Offer 56 - I. 数组中数字出现的次数
题目描述
题意分析
数组中恰好两个不同的数只出现一次，其余数都出现两次。返回这两个数，顺序不限；题目要求时间复杂度为 $O(n)$、额外空间为 $O(1)$，不能靠哈希表统计次数。
解法：异或分组
核心思路
[!blue]
异或满足
x ^ x = 0、x ^ 0 = x，并且可以交换顺序。把所有元素异或，成对出现的数都会抵消，只剩两个答案的异或xor = a ^ b。它还不能直接给出a和b，但能告诉我们它们在哪些位不同。两个答案不同，所以
xor != 0，至少有一位为 1。选其中一位作为标记，把原数组按这一位是 0 还是 1 分组：两个答案一定分开，而两次出现的相同数字一定留在同组。于是每组都只剩一个单次出现的数，分别异或即可得到两个答案。代码用
lowbit = xor & -xor选最低的那一位 1。补码取负相当于按位取反再加 1，最低的 1 被保留，它下方仍为 0，上方与原数互补，因此按位与后只剩这个标记位。
解题步骤
- 第一遍遍历数组，将所有元素异或到
xor中。- 计算
lowbit = xor & -xor，初始化两个异或累加值a = 0、b = 0。- 第二遍遍历，若
(num & lowbit) == 0，异或到a；否则异或到b。- 两组中的成对元素抵消后，返回
a和b。
代码实现
class Solution {
// 取 xor 的最低位 1 作为分组标记，将数组分成两组。
public int[] singleNumbers(int[] nums) {
int xor = 0;
for (int num : nums) {
xor ^= num;
}
// 选取两个答案不同的一位，保证它们进入不同组。
int lowbit = xor & -xor;
int a = 0;
int b = 0;
for (int num : nums) {
// 相同数必然同组，在各自组内成对抵消。
if ((num & lowbit) == 0) {
a ^= num;
} else {
b ^= num;
}
}
return new int[] {
a,
b
};
}
}
func singleNumbers(nums []int) []int {
// 取 xor 的最低位 1 作为分组标记，将数组分成两组。
xor := 0
for _, num := range nums {
xor ^= num
}
// 选取两个答案不同的一位，保证它们进入不同组。
lowbit := xor & -xor
a, b := 0, 0
for _, num := range nums {
// 相同数必然同组，在各自组内成对抵消。
if num&lowbit == 0 {
a ^= num
} else {
b ^= num
}
}
return []int{
a,
b,
}
}
复杂度分析
- 时间复杂度：$O(n)$，其中
n为数组长度；遍历数组两次。- 空间复杂度：$O(1)$，只保存若干整数，不实际创建两个分组数组。
关键点总结
[!green]
- 最低置位只是方便选择，任意异或结果中的置位都能分开答案。
- 分组同时满足相同数不分开、两个答案被分开。
易错点总结
[!yellow]
- 检测标记位要判断
(num & lowbit) != 0，不能要求结果等于 1，标记位不一定是最低第 0 位。xor & (xor - 1)会清除最低的 1，并不是提取它；提取应使用xor & -xor。- 分组依据必须是两个答案不同的那一位，随意选一位可能把两个答案分到同组。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 136. 只出现一次的数字 | 简单 | 本题先根据两个单次值的异或差异位分组，再在每组复用原题的异或抵消。 |
| 137. 只出现一次的数字 II | 中等 | 同样处理少量例外值，原题其他值出现三次，本题其他值出现两次但例外有两个。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！