题目描述

blablabla

样例

blablabla

算法1

(遍历一遍) $O(n)$

• 记录每一个位上面1的个数
• 除以三的余数就是要找的那个唯一数对于二进制位置上的数

C++ 代码

class Solution {
public:
    int findNumberAppearingOnce(vector<int>& nums) {
        if(nums.size() ==0)return -1;
        int bitSum[32]= {0};

        for(int i = 0; i < nums.size();i++){
            int bitMask  = 1;
            for(int j = 31; j >=0; j--){
                int bit = nums[i] & bitMask;
                if(bit != 0)
                    bitSum[j] += 1;
                bitMask = bitMask <<1;
            }
         }
         int res = 0;
         for(int i = 0; i < 32; ++i){
             res = res << 1;
             res += bitSum[i] % 3;//
         }
         return res;
    }
};