LeetCode 137中等位运算
只出现一次的数字 II 图解题解
这道题到底在问什么
给定一个整数数组 nums，其中除了某个元素只出现一次以外，其余每个元素均出现三次。找出并返回那个只出现一次的元素，要求线性时间、常数额外空间。
- 输入
- nums = [5,5,5,7]
- 输出
- 7（5 出现三次，7 只出现一次）
最优解：一步一步想明白
- 3思路一句话：每一位上 1 的个数对 3 取余，余几答案这一位就是几。出现三次的数贡献的 1 被 3 整除自动抵消。下面一步步演给你看。
- 4开始前，先把数字翻成二进制。5 是 101，7 是 111，所以只有最低三位（第 0、1、2 位）需要统计。
- 5现在专门数第 0 位。准备一个计数器 count = 0，指针从头扫到尾，凡这一位是 1 就 count 加一。
- 6指针走到下标 0，nums[0] = 5，二进制 101。它的第 0 位是 1。是 1，count 要加一。
- 7第 0 位是 1，count 加一变成 1（绿色标的都是这一位为 1 的数）。
- 8指针走到下标 1，nums[1] = 5，二进制 101。它的第 0 位是 1。是 1，count 要加一。
- 9第 0 位是 1，count 加一变成 2（绿色标的都是这一位为 1 的数）。
- 10指针走到下标 2，nums[2] = 5，二进制 101。它的第 0 位是 1。是 1，count 要加一。
- 11第 0 位是 1，count 加一变成 3（绿色标的都是这一位为 1 的数）。
- 12指针走到下标 3，nums[3] = 7，二进制 111。它的第 0 位是 1。是 1，count 要加一。
- 13第 0 位是 1，count 加一变成 4（绿色标的都是这一位为 1 的数）。
- 14第 0 位数完，count = 4。对 3 取余得 1，所以答案在第 0 位上就是 1。出现三次的数贡献的 1 刚好被 3 整除抵消了。
- 15现在专门数第 1 位。准备一个计数器 count = 0，指针从头扫到尾，凡这一位是 1 就 count 加一。
- 16指针走到下标 0，nums[0] = 5，二进制 101。它的第 1 位是 0。是 0，count 不变，跳过。
- 17指针走到下标 1，nums[1] = 5，二进制 101。它的第 1 位是 0。是 0，count 不变，跳过。
- 18指针走到下标 2，nums[2] = 5，二进制 101。它的第 1 位是 0。是 0，count 不变，跳过。
- 19指针走到下标 3，nums[3] = 7，二进制 111。它的第 1 位是 1。是 1，count 要加一。
- 20第 1 位是 1，count 加一变成 1（绿色标的都是这一位为 1 的数）。
- 21第 1 位数完，count = 1。对 3 取余得 1，所以答案在第 1 位上就是 1。出现三次的数贡献的 1 刚好被 3 整除抵消了。
- 22现在专门数第 2 位。准备一个计数器 count = 0，指针从头扫到尾，凡这一位是 1 就 count 加一。
- 23指针走到下标 0，nums[0] = 5，二进制 101。它的第 2 位是 1。是 1，count 要加一。
- 24第 2 位是 1，count 加一变成 1（绿色标的都是这一位为 1 的数）。
- 25指针走到下标 1，nums[1] = 5，二进制 101。它的第 2 位是 1。是 1，count 要加一。
- 26第 2 位是 1，count 加一变成 2（绿色标的都是这一位为 1 的数）。
- 27指针走到下标 2，nums[2] = 5，二进制 101。它的第 2 位是 1。是 1，count 要加一。
- 28第 2 位是 1，count 加一变成 3（绿色标的都是这一位为 1 的数）。
- 29指针走到下标 3，nums[3] = 7，二进制 111。它的第 2 位是 1。是 1，count 要加一。
- 30第 2 位是 1，count 加一变成 4（绿色标的都是这一位为 1 的数）。
- 31第 2 位数完，count = 4。对 3 取余得 1，所以答案在第 2 位上就是 1。出现三次的数贡献的 1 刚好被 3 整除抵消了。
- 32把各位拼起来：第2位=1 第1位=1 第0位=1，二进制 111 就是十进制 7。那个只出现一次的数找到了。
⚠️ 容易写错的地方
✗ 错：用哈希表计数找出现一次的
✓ 对：逐位统计 + 对 3 取余
哈希表是 O(n) 额外空间，违反题目“常数空间”要求
✗ 错：把统计的 1 个数对 2 取余
✓ 对：对 3 取余（因为每个数出现三次）
本题重复次数是 3 不是 2，异或那套只适用于出现两次的版本（136 题）
✗ 错：忽略负数 / 第 31 位符号位
✓ 对：统计满 32 位，必要时还原补码
负数的最高位是符号位，只数低位会得到错误结果
完整代码（Python / C++ / Java）
Python
def singleNumber(nums):
ans = 0
for b in range(32): # 逐位统计
cnt = 0
for x in nums:
cnt += (x >> b) & 1 # 这一位是不是 1
if cnt % 3: # 余 1 → 答案这一位为 1
ans |= 1 << b
return ans - (1 << 32) if ans >= 1 << 31 else ans # 处理负数C++
int singleNumber(vector<int>& nums){
int ans = 0;
for (int b = 0; b < 32; b++) {
int cnt = 0;
for (int x : nums) cnt += (x >> b) & 1;
if (cnt % 3) ans |= (1 << b);
}
return ans;
}Java
public int singleNumber(int[] nums) {
int ans = 0;
for (int b = 0; b < 32; b++) {
int cnt = 0;
for (int x : nums) cnt += (x >> b) & 1;
if (cnt % 3 != 0) ans |= (1 << b);
}
return ans;
}复杂度
时间
O(n)
位数 32 是常数，对每一位扫一遍数组，总共 32×n 次，即线性
空间
O(1)
只用 ans、count 几个整数变量，不开哈希表或额外数组
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 只出现一次的数字 II 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
和 136 题（只出现一次的数字 I）有什么区别？+
136 题其余元素出现两次，用异或一遍即可（相同消去）。本题出现三次，异或消不掉，所以改成逐位对 3 取余。
如果其余元素出现 k 次（k 任意），怎么推广？+
把“对 3 取余”改成“对 k 取余”即可：每一位上 1 的总数对 k 取余，余下的就是答案这一位。
有没有 O(1) 空间但不用 32 次循环的位运算解法？+
有，用 ones、twos 两个变量做状态机：ones ^= x & ~twos; twos ^= x & ~ones，最终 ones 即答案。原理仍是“逢三归零”。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄把 只出现一次的数字 II 一步步讲透（全站已上线 905 份讲透，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。