961. 在長度 2N 的數組中找出重複 N 次的元素

思路

題目要求找出重複出現的數字，這個數字 $x$ 出現了 $n$ 遍，
不同的數字一共有 $n + 1$ 個，根據鴿籠定理，取前面 $n + 2$ 個數字出來，一定至少有兩個 $x$。 所以只要檢查前面 $n + 2$ 個數字就行了。

程式碼

1. 哈希表

class Solution {
public:
    int repeatedNTimes(vector<int>& nums) {  
        unordered_map<int, bool> umap;
        for(int num : nums) {
            if(umap.contains(num)) {
                return num;
            }
            umap[num] = true;
        }
        return 0; // impossible;
    }
};

2. 位圖

class Solution {
public:
    int repeatedNTimes(vector<int>& nums) {  
        int n = nums.size();
        vector<int> bset((1e4 + 31) / 32);
        for(int num : nums) {
            if((bset[num / 32] >> (num % 32) & 1) == 1) {
                return num;
            }
            bset[num / 32] |= 1 << (num % 32);
        }
        return 0; // impossible
    }
};

複雜度分析

• 時間複雜度：$O(n)$
• 空間複雜度：$O(n)$