Leetcode: N-Repeated Element in Size 2N Array

N-Repeated Element in Size 2N Array



Similar Problems:


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:

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

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.


// Blog link: https://code.dennyzhang.com/n-repeated-element-in-size-2n-array
// Basic Ideas: the distance could be either 1 or 2, or in the two ends
// Complexity: Time O(n), Space O(1)
func repeatedNTimes(A []int) int {
    for i, val := range A {
        if i == 0 { continue }
        if val == A[i-1] { return val }
        if i>=2 && val == A[i-2] { return val }
    }
    return A[0]
}
linkedin
github
slack

Share It, If You Like It.

Leave a Reply

Your email address will not be published.