LeetCode LCR 004. 只出现一次的数字 II
题目描述
题意分析
数组中恰好一个值只出现一次，其他每个值都出现三次，返回这个单次出现的值。数值允许为零或负数，解法按 32 位有符号整数的补码处理。
目标是线性时间、常数额外空间。普通异或只能消去成对重复，三个相同值异或后仍保留自身，不能直接用于这道题；需要让三次重复的贡献归零。
解法：逐位计数对 3 取余
核心思路
[!blue]
把每个整数看成 32 个独立的二进制位。固定某一位时，一个出现三次的值会贡献零个或三个一，所以所有重复值在这一位的计数之和都是三的倍数。
只出现一次的目标值在这一位仅贡献零或一。因此，将本位的一的总数对三取余，就恰好得到目标值的这一位。依次求出全部余数，再把它们移回对应位置并按位或到
answer，即可还原答案。代码用
(x >> i) & 1提取第i位。即使负数采用算术右移，符号扩展也不会改变这里最后选出的原第i位，因此正负输入可以按同一方式统计。第 31 位同样参与取余与拼接，才能保留负数的补码符号。Java 的
int本身就是 32 位，直接组装即可；Go 用int32保存结果位模式，再转换成返回类型int，避免在 64 位环境中把仅设置第 31 位的无符号大小误当成正数。每一位的计数独立清零，固定处理 32 位，每位扫描整个数组。只保存当前位计数与答案，无需为每个不同数分配记录；答案为零时，所有余数都为零，初始值自然正确。
解题步骤
- 初始化答案为零，枚举第零位到第三十一位。
- 当前位的计数从零开始，扫描所有数并累加
(x >> i) & 1。- 将计数对三取余，左移回第
i位后按位或入答案。- 完成全部位后返回结果，Go 按
int32的有符号值转换。
代码实现
class Solution {
public int singleNumber(int[] nums) {
int answer = 0;
// 32 位必须跑满，第 31 位是符号位，截断会算错负数答案。
for (int i = 0; i < 32; ++i) {
int cnt = 0;
for (int x : nums) {
cnt += x >> i & 1;
}
// 出现三次的元素在这一位上的贡献是 3 的倍数，取余后被整体抹掉。
cnt %= 3;
answer |= cnt << i;
}
return answer;
}
}
func singleNumber(nums []int) int {
var answer int32
for i := 0; i < 32; i++ {
cnt := 0
for _, x := range nums {
cnt += x >> i & 1
}
cnt %= 3
answer |= int32(cnt) << i
}
return int(answer)
}
复杂度分析
- 时间复杂度：$O(32n) = O(n)$，整数位宽固定，每位完整扫描一次数组。
- 空间复杂度：$O(1)$，只使用当前位、当前计数和结果等固定变量。
关键点总结
[!green]
- 重复项的贡献在每一位上都是三的倍数，模三只留下目标位。
- 各位独立处理，不能先把整个整数相加后对三取余。
- 符号位也按同一规则恢复，不能先取绝对值或只处理低三十一位。
- Go 的结果类型明确为
int32，用它恢复题目要求的符号。
易错点总结
[!yellow]
- 直接异或全部值不能抵消三次重复。
- 忽略符号位会把负数答案还原成不相符的非负值。
- 每一位都要重新统计，再对三取余，不能沿用上一位的计数。
- 先将未取余的计数移回去，会把出现次数当作答案位并污染其他位。
- Go 若直接按宽
int组装低三十二位，需注意符号不会自动按三十二位解释。
相似题目
| 题目 | 难度 | 关联与区别 |
|---|---|---|
| 136. 只出现一次的数字 | 简单 | 原题其他值出现两次，可直接异或；本题出现三次，要按位统计模3或用状态机。 |
| 260. 只出现一次的数字 III | 中等 | 同样寻找少数例外值，原题有两个单次值，可按异或差异位分组。 |
转载与许可
许可
本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！