Problem:
N-Repeated Element in Size 2N Array
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:
We can iterate the array, count each element. The counting can be stored in HashMap datastructure, so that put and get cost O(1).
import java.util.*;
class Solution {
public static void main(String...args) {
int[] arr = new int[]{2,1,2,5,3,2};
int result = solve(arr);
System.out.println(result);
}
private static int solve(int[] arr) {
Map<Integer, Integer> map = new HashMap<>();
for(int i : arr) {
map.put(i, map.getOrDefault(i, 0) + 1);
}
for(Integer i : map.keySet()) {
if(map.get(i) == arr.length/2)
return i;
}
return Integer.MIN_VALUE;
}
}
class Solution {
public static void main(String...args) {
int[] arr = new int[]{2,1,2,5,3,2};
int result = solve(arr);
System.out.println(result);
}
private static int solve(int[] arr) {
Map<Integer, Integer> map = new HashMap<>();
for(int i : arr) {
map.put(i, map.getOrDefault(i, 0) + 1);
}
for(Integer i : map.keySet()) {
if(map.get(i) == arr.length/2)
return i;
}
return Integer.MIN_VALUE;
}
}
Since we need to iterate the array once and iterate the HashMap once, the time complexity is O(N), the space complexity is O(N) due to the extra space for the HashMap.
