数组中唯一只出现一次的数字

思路

如果一个数字出现 3 次，那么它的二进制表示的每一位也出现三次，如果把所有出现三次的数字的二进制表示的每一位都分别加起来，那么每一位的和都能被 3 整除

1. cnt[32] 数组存储每一位 1 出现的次数
2. 遍历数组中所有数，将其二进制表示记录在 cnt 数组里
3. 遍历 cnt 数组，根据 cnt[i] 能否被 3 整除，推断出答案的二进制的第 i 位是 0 还是 1

复杂度分析

时间复杂度 O(32n)，空间复杂度用到了长度为 32 的辅助数组，O(1)

代码

class Solution {
public:
    int findNumberAppearingOnce(vector<int>& nums) {
        int cnt[35];//cnt[i]记录二进制第i位1的个数
        memset(cnt,0,sizeof cnt);
        for(auto num:nums)
        {
            for (int i = 0; i < 32; i ++ )            
                if(num>>i&1)    cnt[i]++;
        }
        
        int res=0;
        for (int i = 0; i < 32; i ++ )
            if(cnt[i]%3)//res二进制第i位为1
                res+=1<<i;
        return res;
    }
};