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

自己的代码

class Solution {
    public int repeatedNTimes(int[] A) {
        Map<Integer, Integer> map
                = new HashMap<Integer, Integer>();        
        for(int tmp:A){
            if(map.containsKey(tmp)){
                return tmp;
            }else{
                map.put(tmp,0);
            }
        }
        return 0;
    }
}

Runtime: 1 ms, faster than 79.04% of Java online submissions for N-Repeated Element in Size 2N Array.
Memory Usage: 38.8 MB, less than 99.04% of Java online submissions for N-Repeated Element in Size 2N Array.

官方解法1，该算饭非常慢，不好参考

class Solution {
    public int repeatedNTimes(int[] A) {
        Map<Integer, Integer> count = new HashMap();
        for (int x: A) {
            count.put(x, count.getOrDefault(x, 0) + 1);
        }

        for (int k: count.keySet())
            if (count.get(k) > 1)
                return k;

        throw null;
    }
}

Runtime: 21 ms, faster than 19.01% of Java online submissions for N-Repeated Element in Size 2N Array.
Memory Usage: 40.3 MB, less than 83.31% of Java online submissions for N-Repeated Element in Size 2N Array.

官方解法2

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

        throw null;
    }
}

Runtime: 0 ms, faster than 100.00% of Java online submissions for N-Repeated Element in Size 2N Array.
Memory Usage: 38.8 MB, less than 99.04% of Java online submissions for N-Repeated Element in Size 2N Array.

思考：
1、长度为2N，N+1唯一的数值，然后有一个数值重复N次

解题思路：
1、想把数组拆分长度为2的子集。某个子集会出现以下两种情况
a、该子集不包含该重复值，则必定有一个子集包含两个，则i==i+1
b、该子集包含该重复值，如果相邻的子集不包含该值，则会出现a情况。
响铃有值，则只有存在以下情况： abad、adba。则i==i+2和i==i+3情况。