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 <= 100000 <= A[i] < 10000A.length is evenstruct Solution;
use std::collections::HashSet;
impl Solution {
fn repeated_n_times(a: Vec<i32>) -> i32 {
let mut hs: HashSet<i32> = HashSet::new();
for x in a {
if !hs.insert(x) {
return x;
}
}
unreachable!()
}
}
#[test]
fn test() {
let a = vec![1, 2, 3, 3];
assert_eq!(Solution::repeated_n_times(a), 3);
let a = vec![2, 1, 2, 5, 3, 2];
assert_eq!(Solution::repeated_n_times(a), 2);
let a = vec![5, 1, 5, 2, 5, 3, 5, 4];
assert_eq!(Solution::repeated_n_times(a), 5);
}