面试经典150题 P137 只出现一次的数字 II

---

时间轴

时间轴

2025-11-25

init

位操作

---

题目：

P137 只出现一次的数字 II

https://leetcode.cn/problems/single-number-ii/description/?envType=study-plan-v2&envId=top-interview-150

对于异或，如果数字 x 出现多次：

x ^ x = 0
x ^ x ^ x = x
x ^ x ^ x ^ x = 0
…
所以：偶数个 ⇒ 抵消成 0，奇数个 ⇒ 剩下 1 个 x
可以从更深层的角度理解： XOR 是一种 “mod 2 的无进位加法”

例如：

• 1 ^ 1 = (1 + 1) mod 2 = 0
• 1 ^ 1 ^ 1 = (1 + 1 + 1) mod 2 = 1
  完全符合：
• 偶数次 → mod 2 = 0
• 奇数次 → mod 2 = x

而题目其他数字出现三次，我们需要取模 3：

• 对于每一个比特位（0/1），三个相同数字中，这一位出现了三次：
  • 若这一位是 0：0+0+0 = 0 (mod 3)
  • 若这一位是 1：1+1+1 = 3 ≡ 0 (mod 3)

这整个过程等价于：对每一位相加并进行模 3 运算。

#include <vector>
using std::vector;

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ans = 0;
        int total = 0;
        for (int i = 0; i < 32; ++i) {
            total = 0;
            for (int num: nums)
                total += ((num >> i) & 0x1);

            if (total % 3)
                ans |= (0x1 << i);

        }
        return ans;
    }
};