【leetcode】【剑指offer Ⅱ】004. 只出现一次的数字

• 给定一个整数数组 nums，除某个元素仅出现一次外，其余每个元素都恰出现三次，找出并返回那个只出现了一次的元素。

• 该题仍然是考察位运算，但并非利用异或（如果题目中的要求提及其他元素恰出现两次，则可以利用异或操作来解题）。
  • 把每个整数看成二进制表达形式，当同一个数出现三次，则可以看作将对应位上的 0 或 1 出现三次。
  • 遍历每个数值，将数值对应的 32 位二进制出现的 1 出现的次数进行对应位置上的累加（累加到一个 32 位数组中进行保存）。
  • 遍历完成后从 32 位的数组中取出每一位上的数值，并将每一位进行 mod 3 操作然后提取出对应位上的 0 或 1 即可。

class Solution
{
public:
    int singleNumber(vector& nums)
    {
        vector cnt(32);
        for(int i = 0; i < 32; ++i)
        {
            for(int num : nums)
                cnt[i] += (num >> i) & 1;
        }
        int ans = 0;
        for(int i = 31; i >= 0; --i)
            ans = (ans << 1) + (cnt[i] % 3);
        return ans;
    }
};