leetcode11_137. 只出现一次的数字 II

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现了一次的元素。

说明：

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

思路1（普通）:
可以用hashmap来实现,

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        unordered_map<int,int> result;
        for(int i=0;i<nums.size();i++)
        {
            result[nums[i]]++;
        }
        for(auto n:result)
        {
            if(n.second==1)
                return n.first;
        }
        return 0;
    }
};

用unordered_map而不用hash_map的原因时，unordered_map被写进了标准库。
思路二（神奇）：
由题目可得，出现数字的次数只有三次和一次。
我们把每个数字看出二进制，所以就有32位，假设第i位，将数组中的所有的数字的第i位相加，最后结果肯定是3的倍数或者3N+1，所以我们把每一位对三取余，就可以找的只出现一次的数在第i位的数。

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int temp[32]={0};
        int result=0;
        for(int i=0;i<32;i++)
        {
            for(auto j:nums)
            {
                temp[i]+=(j>>i)&1;
            }
            temp[i]%=3;
        }
        for(int i=0;i<32;i++)
        {
            result |= temp[i]<<i;
        }
        return result;
    }
};

这里使用了一个数组，还可以继续优化，将temp数组去掉

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int result=0;
        for(int i=0;i<32;i++)
        {
            int temp=0;
            for(auto j:nums)
            {
                temp+=(j>>i)&1;
            }
            result |= (temp%3)<<i;
        }
        return result;
    }
};