137 -Single Number II

Single Number II

Given an array of integers, every element appears three times except for one. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

Hide Tags

Bit Manipulation

Hide Similar Problems

(M) Single Number

用数组统计每个bit位的出现次数，对3求余，

所有出现过三次的数字的bit位都会被去掉，

剩下的bit位就是只出现过依次的那个数字，重新组合即可。

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int sz = nums.size();
        int rst = 0;
        if(sz)
        {
            int bits[32]={0};
            for(int ii=0; ii<sz; ++ii)
            {
                int num = nums[ii];
                for(int bb=0; bb<32; ++bb)
                {
                    if(num&(1<<bb))
                        bits[bb]++;
                }
            }
           
            for(int bb=0; bb<32; ++bb)
            {
                if((bits[bb])%3)
                    rst |= (1<<bb);
            }
        }
        return rst;
    }
};

16 ms.