137. 只出现一次的数字 II

Introduction

Question：137. 只出现一次的数字 II

Analysis

解法一：hashmap 统计个数，然后遍历 HashMap 确定那个值只出现了一次
时间复杂度为 O(n)，空间复杂度为 O(n)

已 [4, 4, 3, 4] 为例子，为了方便，所有数字的二进制表示都只保留后 4 bit。
4 的二进制表示为 0100
3 的二进制表示为 0011
而我们的答案就是 3。

我们可以在二进制表示上做 HashMap，即统计每一位中 1 出现的个数。
可以很容易的发现，对于第 k 位来说，如果 1 出现的个数不为 3 的倍数，那么答案的二进制表示中第 k 位一定为 1
而如果 1 出现的个数为 3 的倍数，那么答案的二进制表示中第 k 位一定为 0。
因为题目限定了只有 32 位的数字出现，所以 hashmap 可以用大小为 32 的数组代替。
空间复杂度为 O(n)，时间复杂度为 O(n)。

Implement

int singleNumber(vector<int>& nums) {
    vector<int> count(32);
    for(auto &n: nums) {
        for(int i = 0;i < 32;i++) {
            count[i] += !(n & (1 << i));
        }
    }
    int res = 0;
    for(int i = 0;i < 32;i++) {
        // if (count[i] % 3) res |= (1 << i);
        res |= ((!(count[i] % 3)) << i);
    }
    return res;
}

One More Thing