题目描述

哈希表

看到题目的第一反应就是用哈希表，在c++中是unordered_map。

这里用了一个小技巧，当某个数出现k次后，从哈希表中删除，这样最后哈希表中只会剩下一个数，就是答案。

时间复杂度O(n)，空间复杂度O(n)。

#include <unordered_map>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param arr int整型vector 
     * @param k int整型 
     * @return int整型
     */
    int foundOnceNumber(vector<int>& arr, int k) {
        unordered_map<int, int> mp;
        for(int &i : arr) {
            if(++mp[i] == k) mp.erase(i);
        }
        return mp.begin()->first;
    }
};

位运算

哈希表的一个问题是空间复杂度比较大，当数据量增加的时候，会出现哈希冲突，导致时间复杂度急剧上升。使用位运算可以很好解决这个问题。

注意，数组中只有一个数字出现一次，设为ans，其他所有数字都出现k次。那么将数组中的每个数字看成一个二进制数。由于int是32位的数据类型，所以针对其每一位做一个求和，再对k取余数，就得到了ans在该位的值。

时间复杂度O(32n)，空间复杂度O(1)。

#include <unordered_map>
class Solution {
  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param arr int整型vector
     * @param k int整型
     * @return int整型
     */
    int foundOnceNumber(vector<int>& arr, int k) {
        int ans = 0;
        for (int i = 0; i < 32; ++i) {
            int sum = 0;
            for (int& x : arr) {
                if (x & 1) ++sum;
                x >>= 1;
            }
            if(sum % k) ans += 1 << i;
        }
        return ans;
    }
};