961. Element repeated N times

Difficulty: easy

There are N+1 different elements in array A of size 2N, one of which is repeated N times.

Returns the element that has been repeated N times.

Example 1:

Input: [1,2,3,3] output: 3Copy the code

Example 2:

Input: [2,1,2,5,3,2] Output: 2Copy the code

Example 3:

Input: [5,1,5,2,5,3,5,4] Output: 5Copy the code

Tip:

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

Solution

The first reaction is to use Set to count the number of occurrences of elements. The number of occurrences of each element is recorded. It is natural to use HashMap to solve the problem, so we have the following solution. Language: java

Class Solution {/ / such as I now use A HashMap to do public int repeatedNTimes (int [] A) {if (A = = null | | a. ength < 4) return 1; Map<Integer , Integer> map = new HashMap(); for(int a : A) { map.put(a , map.getOrDefault(a , 0) + 1); } for(map.entry <Integer, Integer> Entry: map.entryset ()) {int value = entry.getValue(); if(value >= A.length / 2 ) { return entry.getKey(); } } return -1; }}Copy the code

Unfortunately, with only over 16% of the submissions, there is still a lot of room for improvement;

class Solution { public int repeatedNTimes(int[] A) { if(A == null || A.length < 4) return -1; Set<Integer> set = new HashSet(); For (int a: a) {if(! set.add(a)) { return a; } } return -1; }}Copy the code