Single Number II

137. 只出现一次的数字II

分析

考虑整数在计算机中以 32 位二进制形式表示，可以逐位统计数组中每个位上的 1 的出现次数

逐位遍历
- 对于每一位 i（从 0 到 31 位），统计所有数字中第 i 位上的 1 的总数 c
模 3 运算
- 若某个位上的 1 的出现次数不是 3 的倍数，则说明这个位在目标数中为 1
- 将该位加入结果 res
结果构建
- 将每一位结果通过位运算 res |= (c % 3) << i 累加到最终结果 res 中

时间复杂度

时间复杂度 O(n)

空间复杂度

空间复杂度为 O(1)

C++代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


class Solution
{
public:
    int singleNumber(vector<int>& nums)
    {
        int res = 0;
        for (int i = 0; i < 32; ++i) // 遍历每一个二进制位
        {
            int c = 0;

            // 统计当前二进制位上 1 的数量
            for (int x : nums)
                c += (x >> i) & 1;

            // 若该二进制位的 1 数量不是 3 的倍数，将该位加入结果
            res |= (c % 3) << i;
        }
        return res;
    }
};