961. 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

Rust Solution

struct 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);
}

Having problems with this solution? Click here to submit an issue on github.