# 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
```

#### 解题要点：

遍历整个数组，当找到有相同数时，返回这个数。

```java
class Solution {
    public int repeatedNTimes(int[] A) {
        for(int i = 1; i <= 3; ++i){
            for(int k = 0; k < A.length - i; ++k)
                if(A[k] == A[k + i]) 
                    return A[k];
        }
        return 0;
    }
}
```

```java
class Solution {
    public int repeatedNTimes(int[] A) {
        Arrays.sort(A);
        for(int i = 0; i < A.length - 1; i++){
            if(A[i] == A[i + 1]) 
                return A[i];
        }
        return 0;
    }
}
```

#### 学习解法：

**Compare**

If we ever find a repeated element, it must be the answer. Let's call this answer the *major element*.

Consider all subarrays of length 4. There must be a major element in at least one such subarray.

This is because either:

* There is a major element in a length 2 subarray, or;
* Every length 2 subarray has exactly 1 major element, which means that a length 4 subarray that begins at a major element will have 2 major elements.

Thus, we only have to compare elements with their neighbors that are distance 1, 2, or 3 away.

```java
class Solution {
    public int repeatedNTimes(int[] A) {
        for(int i = 1; i <= 3; ++i){
            for(int k = 0; k < A.length - i; ++k)
                if(A[k] == A[k + i]) 
                    return A[k];
        }
        return 0;
    }
}
```

**Complexity Analysis**

* Time Complexity: O(N), where N is the length of `A`.
* Space Complexity: O(1).&#x20;