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

在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。

示例 1：

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

示例 2：

1 2	输入：nums = [9,1,7,9,7,9,7] 输出：1

限制：

1 2	1 <= nums.length <= 10000 1 <= nums[i] < 2^31

解法一：哈希表

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        unordered_map<int,int> cmap;
        
        for(int num:nums){
            cmap[num]++;
        }
        for(auto num:cmap){
            if(num.second == 1)return num.first;
        }
        return -1;
    }
};

很暴力

执行用时：
24 ms
, 在所有 C++ 提交中击败了
91.65%
的用户
内存消耗：
18 MB
, 在所有 C++ 提交中击败了
18.44%
的用户
通过测试用例：
32 / 32

解法二:位运算

思路:

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        unordered_map<int,int> cmap;
       
        for(int num:nums){
            bitset<32> t = num;

            auto temp = t.to_string();
            auto size = temp.size();
            for(int j = 0;j<size;j++){
                cmap[j] += temp[size-1-j] == '1' ? 1 : 0;
            }
        }

        string res;
        for(int i = 0;i<32;i++){
            res += to_string(cmap[32-1-i] % 3);
        }

        return bitset<32>(res).to_ulong();
    }
};

结果

执行用时：
116 ms
, 在所有 C++ 提交中击败了
5.31%
的用户
内存消耗：
23.7 MB
, 在所有 C++ 提交中击败了
5.11%
的用户
通过测试用例：
32 / 32

这效率不太行啊

优化一下

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        vector<int> temp(32);
       
        for(int num:nums){
            for(int j = 0;j<32;j++){
                temp[j] += (num>>j & 1) == 1 ? 1:0;
            }
        }

        int res=0;
        for(int i = 31;i>=0;i--){
            res = res<< 1;
            if(temp[i]%3==1) res = res | 1;
        }

        return res;
    }
};

结果好了一点

执行用时：
44 ms
, 在所有 C++ 提交中击败了
26.27%
的用户
内存消耗：
15.8 MB
, 在所有 C++ 提交中击败了
42.66%
的用户
通过测试用例：
32 / 32

深度优化，大佬做法

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int A = 0, B = 0;
        for (int C : nums) {
            int tmp = A;
            A = (B & C) | (A & ~C);
            B = (B & ~C) | (~tmp & ~B & C);
        }
        return B;
    }
};

结果起飞

执行用时：
28 ms
, 在所有 C++ 提交中击败了
80.24%
的用户
内存消耗：
15.7 MB
, 在所有 C++ 提交中击败了
75.95%
的用户