961. N-Repeated Element in Size 2N Array.md

961. N-Repeated Element in Size 2N Array

---

Difficulty : Easy

Related Topics : HashTable

---

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

---

Solution

• mine
  • Java

    • Runtime: 10 ms, faster than 30.82%, Memory Usage: 51.8 MB, less than 30.24% of Java online submissions

      // O(N*logN)time
      // O(1)space
      public int repeatedNTimes(int[] A) {
          Arrays.sort(A);
          int a = A[A.length/2 + 1];
          int b = A[A.length/2];
          int c = A[A.length/2 - 1];
          if(a == b || a == c){
              return a;
          }else{
              return c;
          }
      }
      

    • Runtime: 13 ms, faster than 29.15%, Memory Usage: 39.8 MB, less than 93.07% of Java online submissions

      //O(N)time
      //O(N)space
      public int repeatedNTimes(int[] A) {
          Map<Integer, Integer> map = new HashMap<>();
          int max = 0;
          int res = 0;
          for (int a : A) {
              int t = map.getOrDefault(a, 0) + 1;
              if(t > max){
                  max = t;
                  res = a;
              }
              map.put(a, t);
          }
          return res;
      }
      

---

• the most votes

• Runtime: 1 ms, faster than 67.00%, Memory Usage: 52 MB, less than 22.48% of Java online submissions

  //O(1)time
  //O(1)space
  public int repeatedNTimes(int[] A) {
     int i = 0, j = 0, n = A.length;
      while (i == j || A[i] != A[j]) {
          i = (int)(Math.random() * n);
          j = (int)(Math.random() * n);
      }
      return A[i];
  }
  

---