961

961. N-Repeated Element in Size 2N Array (Easy)

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:

1. 4 <= A.length <= 10000
2. 0 <= A[i] < 10000
3. A.length is even

Related Topics:
Hash Table

Solution 1.

// OJ: https://leetcode.com/problems/n-repeated-element-in-size-2n-array
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(N)
class Solution {
public:
    int repeatedNTimes(vector<int>& A) {
        unordered_set<int> s;
        for (int n : A) {
            if (s.find(n) != s.end()) return n;
            s.insert(n);
        }
    }
};

Solution 2.

For the duplicate number, it either shows side by side (A[i] and A[i + 1]) or alternated(A[i] and A[i + 2]), or at the front and rear like [2, 1, 3, 2].

class Solution {
public:
    int repeatedNTimes(vector<int>& A) {
      for (int i = 0; i < A.size() - 2; ++i) {
          if (A[i + 1] == A[i + 2]) return A[i + 1];
          if (A[i] == A[i + 1] || A[i] == A[i + 2]) return A[i];
      }
      return A[0]; 
    }
};