961. N-Repeated Element in Size 2N Array

Link: https://leetcode.com/problems/big-countries/

In a array A of size 2N, there are N+1 unique elements, and exactly one of these elements is repeated N times.

Return the element repeated N times.

Example 1:

Input: [1,2,3,3]
Output: 3

Example 2:

Input: [2,1,2,5,3,2]
Output: 2

Example 3:

Input: [5,1,5,2,5,3,5,4]
Output: 5

Note:

• 4 <= A.length <= 10000
• 0 <= A[i] < 10000
• A.length is even

---

題目翻譯:

在大小為 2N 的陣列 A 中，存在 N + 1 個唯一元素，並且這些元素中的一個重複 N 次。

返回元素重複 N 次。

程式思路:

雖然題目有限制元素的大小，就可以使用 hash table 來做這題，但覺得還是寫成動態會比較好些，就使用 unordered_map 容器來寫。

class Solution {
public:
    int repeatedNTimes(vector<int>& A) {
        unordered_map <int,int> NTimes_map;
        int output = 0;
        for(auto element : A)
        {
            auto ret = NTimes_map.insert ( std::pair<char,int>(element,0) );
            if (ret.second == false) {
                // std::cout << "element already existed";
                //NTimes_map[element]++;
                output = element;
                break;
            }
        }
        return output;
    }
};