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

解题要点：

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

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

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.

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