leetcode137. 只出现一次的数字 II

题目：

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

你必须设计并实现线性时间复杂度的算法且使用常数级空间来解决此问题。

示例 1：

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

示例 2：

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

核心逻辑：

        计算出数组中所有数的二进制的每一位的1的个数，如果某位上1的个数 %3 等于 0，那么要么有3的倍数个1，要么没有1；如果不等于0，也就是1的个数不是3的倍数。

逐位（从右向左）统计每一位的1的个数：

for(int i=0; i<32; i++)

• 使用一个循环来检查整数的每一位（从第0位到第31位，总共32位，考虑的是整型在二进制中的表示）。

int count = 0;
for(int num : nums)
{
    if((num >>> i & 1) == 1)
    {
        count++;
    }
}

遍历数组中每一个数的第i位（右移i个），如果这个位等于1，count就加1。

判断第 i 位是否属于目标数字：

            if(count % 3 != 0)
            {
                ret = ret | 1<<i;
            }

• 如果 count % 3 != 0，说明目标数字在第 i 位有1（因为其他数字都出现了3次，其1的个数对3取模一定为0）。
• 使用按位或操作 ret | 1<<i 将结果的第 i 位设置为1。

例子：

我们用数组 nums = [2, 2, 3, 2] 来举例分析代码的执行过程，找出只出现一次的数字。

数字的二进制表示：

• 2 的二进制表示是 00000010 （8位只显示低位，实际是32位）
• 3 的二进制表示是 00000011

所以 nums 的二进制形式是：

2: 00000010
2: 00000010
3: 00000011
2: 00000010

按位统计每一位的 1 的个数

我们依次对每一位统计 1 的个数。外层循环遍历 32 位（从第 0 位到第 31 位），每一位的处理过程如下：

第 0 位

看第 0 位（从右向左数）：

2: 00000010 -> 第 0 位是 0
2: 00000010 -> 第 0 位是 0
3: 00000011 -> 第 0 位是 1
2: 00000010 -> 第 0 位是 0

统计：第 0 位有 1 的个数是 1。

count % 3 != 0，所以 ret 的第 0 位是 1。

第 1 位

看第 1 位（从右向左数）：

2: 00000010 -> 第 1 位是 1
2: 00000010 -> 第 1 位是 1
3: 00000011 -> 第 1 位是 1
2: 00000010 -> 第 1 位是 1

统计：第 1 位有 1 的个数是 4。

count % 3 == 0，所以 ret 的第 1 位是 0。

第 2 位

看第 2 位（从右向左数）：

2: 00000010 -> 第 2 位是 0
2: 00000010 -> 第 2 位是 0
3: 00000011 -> 第 2 位是 0
2: 00000010 -> 第 2 位是 0

统计：第 2 位有 1 的个数是 0。

count % 3 == 0，所以 ret 的第 2 位是 0。

其他高位

从第 3 位到第 31 位，所有数字的这一位都是 0，所以统计的 1 的个数都是 0。

count % 3 == 0，所以 ret 的这一位都是 0。

最终结果

合并各个位的结果，ret 的二进制表示是：

00000011

class Solution 
{
public:
    int singleNumber(vector<int>& nums) 
    {
        int ret = 0;
        for(int i=0; i<32; i++)
        {
            int count = 0;//不能放到外面，每一轮都要清零
            for(int num : nums)
            {
                if((num>>i & 1) == 1)
                {
                    count++;
                }
            }
            if(count % 3 != 0)
            {
                ret = ret | 1<<i;
            }
        }
        return ret;
    }
};