时间轴

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 运算，但用位运算实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#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;
    }
};