力扣算法——137SingleNumberII【M】

Given a non-empty array of integers, every element appears three times except for one, which appears exactly once. Find that single one.

Note:

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

Example 1:

Input: [2,2,3,2]
Output: 3

Example 2:

Input: [0,1,0,1,0,1,99]
Output: 99


Solution：
　　因为不能使用额外的空间，不然就可以开辟数组来对数据个数进行统计了
　　那么只能使用位运算了，计算32位中，每个数字出现1的次数，一旦个数不为1，那么该位就是那个唯一数字的位数了

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int bits[32] = { 0 };
        for (int i = 0; i < nums.size(); ++i)
        {
            int c = 1;
            for (int j = 0; j < 32; ++j)
            {
                bits[j] += (c & nums[i]) ? 1 : 0;
                c = c << 1;
            }
        }
        int res = 0;
        for (int i = 0; i < 32; ++i)
            if (bits[i] % 3)
                res += (int)pow(2.0, i);
        return res;
    }
};