计数统计思想

一个int由32位组成，每位都是0/1，基于这样的思想，我们统计每一位0和1出现的次数，这样能够把答案通过二进制构造出来。

1.若第i位1出现次数不是3的倍数，则说明答案在第i位是1

2.否则说明答案在第i位是0

$ 时间复杂度O(N)，空间复杂度O(1) $

参考文献

lc究极班

AC代码

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int res = 0;
        for (int i = 31 ; i >= 0 ; i --){
            //计算第i位1的个数
            int cnt = 0;
            for (auto x : nums){
                if (x >> i & 1) cnt ++;
            }
            //判断i位1出现次数
            if (cnt % 3 == 1){
                res = (res << 1) + 1;
            } else res <<= 1;
        }
        return res;
    }
};