Welcome to Subscribe On Youtube

Question

Formatted question description: https://leetcode.ca/all/961.html

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

Algorithm 1

This question says that there is an array A with a length of 2N. There are N+1 different numbers in it, and one number is repeated exactly N times. Let’s find the number repeated N times. It is not a difficult problem. You can directly use a HashMap to count the number of occurrences of each number. As long as a certain number appears N times, it will return in line with the meaning of the question. But here we can further optimize, because only one number is repeated, and the others are not repeated, so as long as the number of occurrences of a certain number is found to be greater than once, it can be returned directly. See the code as follows:

Code 1

C++

class Solution {
public:
    int repeatedNTimes(vector<int>& A) {
        int n = A.size();
        unordered_map<int, int> numCnt;
        for (int num : A) {
            if (++numCnt[num] > 1) return num;
        }
        return -1;
    }
};

Algorithm 2

Due to the particularity of this question array, half of the numbers are repeated, so as long as there are repeated numbers in three consecutive numbers, it must be what you want. In order to avoid index overflow, we traverse from the third number and find out whether the first two numbers are repeated each time. If there is a repetition, the number will be returned directly. But there are also cases where there is no repetition after the traversal. There are only two cases of [x, x, y, z] or [x, y, z, x], just return the first number directly, see the code as follows:

Code 2

C++

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

• Java
• C++
• Python
• Javascript

• class Solution {
      public int repeatedNTimes(int[] A) {
          Set<Integer> set = new HashSet<Integer>();
          for (int num : A) {
              if (!set.add(num))
                  return num;
          }
          return -1;
      }
  }
  
  ############
  
  class Solution {
      public int repeatedNTimes(int[] nums) {
          Set<Integer> s = new HashSet<>();
          for (int num : nums) {
              if (s.contains(num)) {
                  return num;
              }
              s.add(num);
          }
          return -1;
      }
  }
  

• // OJ: https://leetcode.com/problems/n-repeated-element-in-size-2n-array
  // 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);
          }
      }
  };
  

• class Solution:
      def repeatedNTimes(self, nums: List[int]) -> int:
          s = set()
          for num in nums:
              if num in s:
                  return num
              s.add(num)
  
  ############
  
  class Solution(object):
      def repeatedNTimes(self, A):
          """
          :type A: List[int]
          :rtype: int
          """
          N = len(A) / 2
          count = collections.Counter(A)
          for k, v in count.items():
              if v == N:
                  return k
          return 0
  

• /**
   * @param {number[]} nums
   * @return {number}
   */
  var repeatedNTimes = function (nums) {
      const s = new Set();
      for (const num of nums) {
          if (s.has(num)) {
              return num;
          }
          s.add(num);
      }
      return -1;
  };
  
  

All Problems

All Solutions