LeetCode: 137. 只出现一次的数字 II

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

 

示例 1：

输入：nums = [2,2,3,2]
输出：3
示例 2：

输入：nums = [0,1,0,1,0,1,99]
输出：99
 

提示：

1 <= nums.length <= 3 * 104
-231 <= nums[i] <= 231 - 1
nums 中，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次
 

分析：

       基础题目为该题：136.只出现一次的数字。基础版采用了一个简单的位运算——异或运算。对于多个0和1，它们异或运算的计算，只与0和1的个数有关，与顺序无关。简而言之也就是符合交换律。所以我们只需要对这n个数各位进行异或运算即可。

       而升级版不一样的地方在于只有一个数字出现了一次，其他数字都出现了三次。他们之间的区别在于，出现三次的数字，每一位，要么出现了三次0，要么出现了三次1，出现次数都是三的倍数。于是想到了统计每一位出现的次数，如果不是三的倍数，说明该位属于只出现一次的数字。依据这个思路可以解决该问题，本题重点是对位运算的操作。需要积累一下。

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ans = 0;
        for(int i = 0; i < 32; i++){
            int total = 0;
            for(int num : nums)
                total += num >> i & 1;    //与1相与，可得第i位结果
            if(total % 3 != 0)
                ans = ans | (1 << i);    //第i位置为1
        }
        return ans;
    }
};