【C++算法】36.位运算_只出现一次的数字 II

文章目录

• • 题目链接：
  • 题目描述：
  • 解法
  • C++ 算法代码：
  • 解析

题目链接：

137. 只出现一次的数字 II

题目描述：

解法

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

意外发现出现1次的那个数和所有比特位当前的和%3得到的值一样。

我们就可以求所有比特位当前的和%3得到的值，每一位结合起来就是只出现1次的那个数。

C++ 算法代码：

class Solution 
{
    public:
    int singleNumber(vector<int>& nums) 
    {
        int ret = 0;
        for(int i = 0; i < 32; i++) // 依次去修改 ret 中的每一位
        {
            int sum = 0;
            for(int x : nums) // 计算nums中所有的数的第 i 位的和
            {
                if(((x >> i) & 1) == 1){ // 检查数字 x 的第 i 位是否为1
                    sum++; // 如果是1，累加到 sum 中
                }
            }
            sum %= 3;
            if(sum == 1) // 如果 sum % 3 == 1，说明只出现一次的数字在第 i 位是1
            {
                ret |= 1 << i; // 将 ret 的第 i 位设置为1
            }
        }
        return ret;
    }
};

解析

例如：nums = [2,2,3,2]

1. ret = 0

   遍历每一位
   i = 0（最低位）
   计算 sum：
   2 的第 0 位是 0
2 的第 0 位是 0
3 的第 0 位是 1
2 的第 0 位是 0
sum = 0 + 0 + 1 + 0 = 1
   取模：sum % 3 = 1
   更新 ret：
   因为 sum % 3 == 1，所以将 ret 的第 0 位设置为 1。
   ret = 0 | (1 << 0) = 1（二进制 0001）

2. i = 1（第二位）
   计算 sum：
   2 的第 1 位是 1
2 的第 1 位是 1
3 的第 1 位是 1
2 的第 1 位是 1
sum = 1 + 1 + 1 + 1 = 4
   取模：sum % 3 = 1
   更新 ret：
   因为 sum % 3 == 1，所以将 ret 的第 1 位设置为 1。
   ret = 1 | (1 << 1) = 3（二进制 0011）

3. i = 3 到 31（高位）
   对于这些位，nums 中所有数字的对应位都是 0，所以 sum = 0，sum % 3 = 0，ret 的这些位保持 0。

4. ret = 3（二进制 0011）
   这些位，nums 中所有数字的对应位都是 0，所以 sum = 0，sum % 3 = 0，ret 的这些位保持 0。

5. ret = 3（二进制 0011）