剑指 Offer 56 - II. 数组中数字出现的次数 II-526互联

方法一：位运算

解题思路

由题意知，其他数值都出现了三次，那么其数值二进制位上的$1$也至少出现了三次，那么我们可以统计数值每一位上$1$的个数的总和，然后遍历每一位上$1$的数量，若某一位上的$1$的数量不能被$3$整除，说明只出现一次的数字的二进制位在该位上为$1$，将该位置为1，直到结束。

代码

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int bit[32]; memset(bit, 0, sizeof(bit));
        for (auto &num : nums) {
            int k = 0;
            while (k < 32) {
                bit[k] += num >> k & 1;
                k ++ ;
            }
        }
        int res = 0;
        for (int k = 0; k < 32; k ++ ) {
            if (bit[k] % 3 != 0) {
                res |= 1 << k;
            }
        }
        return res;
    }
};

复杂度分析

时间复杂度：$O(n)$；
空间复杂度：$O(1)$。

方法二：逻辑电路

解题思路

我们可以将数组中的每个数字在二进制下的每一位看做是一个线路，每个线路上只能有 $0$ 或 $1$ 两种信号。如果一个数字出现了三次，那么对应的线路上就应该接入三个$“1”$的信号，否则就接入一个$“1”$的信号。接下来我们可以使用逻辑电路来统计每个线路上的$“1”$的个数，如果个数不能被 $3$ 整除，那么说明只出现一次的数字在该线路上的值是 $1$，否则就是 $0$。最后我们将每个线路上的值组合起来，就可以得到只出现一次的数字。
现在，我们考虑使用异或运算和位运算来实现对每个数出现的次数的计数。由于一个数出现 $3$ 次就会被抵消掉，因此我们需要使用两个状态变量来记录每个二进制位上$“1”$的个数模 $3$ 的余数为 $1$ 和 $2$ 时的情况，即 $ones$ 和 $twos$ 变量。初始状态下，$ones$ 和 $twos$ 都应该是 $0$。
对于每个新的数 $nums[i]$，我们首先需要更新 $ones$ 的状态。如果 $ones$ 的对应位是 $0$，且 $nums[i]$ 的对应位也是 $0$，那么 $ones$ 的对应位就变成了 $0$；如果 $ones$ 的对应位是 $0$，且 $nums[i]$ 的对应位是 $1$，那么 $ones$ 的对应位就变成了 $1$；如果 $ones$ 的对应位是 $1$，且 $nums[i]$ 的对应位也是 $1$，那么 $ones$ 的对应位就变成了 $0$；如果 $ones$ 的对应位是 $1$，且 $nums[i]$ 的对应位是 $0$，那么 $ones$ 的对应位就变成了 $1$。可以用以下的公式来表示：ones = (ones ^ nums[i]) & ~twos;其中，~$twos$ 表示将 $twos$ 中的每个二进制位取反，使得在 $twos$ 中对应位置上是 $0$ 的位在 $ones$ 中对应位置上也是 $0$。
接下来，我们需要更新 $twos$ 的状态。如果 $twos$ 的对应位是 $0$，且 $ones$ 的对应位也是 $0$，那么 $twos$ 的对应位就变成了 $0$；如果 $twos$ 的对应位是 $0$，且 $ones$ 的对应位是 $1$，那么 $twos$ 的对应位就变成了 $1$；如果 $twos$ 的对应位是 $1$，且 $ones$ 的对应位也是 $1$，那么 $twos$ 的对应位就变成了 $0$；如果 $twos$ 的对应位是 $1$，且 $ones$ 的对应位是 $0$，那么 $twos$ 的对应位就变成了 $1$。可以用以下的公式来表示： $twos = (twos ^ nums[i]) & ~ones;$ 同样，~$ones$ 表示将 $ones$ 中的每个二进制位取反，使得在 $ones$ 中对应位置上是 $0$ 的位在 $twos$ 中对应位置上也是 $0$。
最后，我们只需要返回 $ones$ 变量的值，即为只出现一次的数字。
总结一下，这种解法利用了数字电路中的异或运算和位运算。通过维护两个状态变量 $ones$ 和 $twos$，分别记录每个二进制位上$“1”$的个数模 $3$ 的余数为 $1$ 和 $2$ 时的情况，来实现对每个数出现的次数的计数。由于每个数出现 $3$ 次就会被抵消掉，因此最终得到的 $ones$ 就是只出现一次的数字。这种解法的时间复杂度为 $O(n)$，空间复杂度为 $O(1)$。

代码

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ones = 0, twos = 0;
        for (int i = 0; i < nums.size(); i++) {
            ones = (ones ^ nums[i]) & ~twos;
            twos = (twos ^ nums[i]) & ~ones;
        }
        return ones;
    }
};

复杂度分析

时间复杂度：$O(n)$；
空间复杂度：$O(1)$。