[LeetCode]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?

使用hash table可以，但是使用了额外的空间。

要想不使用额外空间，可以运用位运算。

所有和出现次数的题目都可以用位运算，Majority Element也可以的。

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int result=0;
        vector<int> bit(32,0);
        for(int i=0;i<nums.size();i++)
        {
            int temp = nums[i];
            for(int j =0;j<32;j++)
            {
                bit[j]+=((temp>>j) & 0x01);
                bit[j]%=3;
            }
        }
        for(int j=0;j<32;j++)
        {
            result+=bit[j]<<j;
        }
        return result;
    }
};