【位运算】数组中出现的次数为一的数字

有一个数字只出现了一次

其余数字都出现了两次，找到这个数，要求\(O(1)\)空间复杂度。

全部异或一遍即可。

有两个数字只出现了一次

其余数字都出现了两次，找到这个数，要求\(O(1)\)空间复杂度。

分组异或。考虑这两个数为a, b，我们可以得到a ^ b，然后任选一个为一bit作为分组依据。

class Solution {
public:
    vector<int> singleNumbers(vector<int>& nums) {
        int a = 0, b = 0, i = 0;
        for (int x: nums) a ^= x;
        while ((a & (1<<i)) == 0) i++;
        a = 0;
        for (int x: nums) {
            if (x & (1<<i)) a ^= x;
            else b ^= x;
        }
        return {a, b};
    }
};

有一个数字只出现了一次，其余数字都出现了三次

要求\(O(1)\)空间复杂度。

计算每个bit出现的次数，取模即可。

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int v[32] = {0};
        for (int x: nums) {
            for (int i = 0; i < 32; i++) {
                if (x & (1 << i)) v[i] = (v[i] + 1) % 3;
            }
        }
        int ans = 0;
        for (int i = 0; i < 32; i++) {
            if (v[i]) ans |=(1 << i);
        }
        return ans;
    }
};

高级做法：

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int c1 = 0, c2 = 0;
        for (int x: nums) {
            c1 = c1 ^ x & ~c2;
            c2 = c2 ^ x & ~c1;
        }
        return c1;
    }
};

有一个数字只出现了一次，其余数字都出现了m次

要求\(O(1)\)空间复杂度。

第二种方法通解。

class Solution {
public:
    int singleNumber(vector<int>& nums, int m) {
        int v[32] = {0};
        for (int x: nums) {
            for (int i = 0; i < 32; i++) {
                if (x & (1 << i)) v[i] = (v[i] + 1) % m;
            }
        }
        int ans = 0;
        for (int i = 0; i < 32; i++) {
            if (v[i]) ans |=(1 << i);
        }
        return ans;
    }
};