关注 每天一道编程题 专栏，一起学习进步。

题目

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

分析

题意：长度为2N的数组，其中N+1个都是唯一的，有一个重复N次的数，将其找出来。

算法：
创建一个长度为10000的数组tmp
遍历所给数组A，将tmp[i]++
如果tmp[i]==A.length/2，A返回

解答

class Solution {
    public int repeatedNTimes(int[] A) {
        int [] tmp =new int[10000];
        for(int i:A){
            tmp[i]++;
            if(tmp[i]==A.length/2){
                return i;
            }
        }
        return -1;
    }
}

上述算法复杂度太高
看看评论区的解答

class Solution {
        public int repeatedNTimes(int[] A) {
        int[] count = new int[10000];
        for (int a : A)
            if (count[a]++ == 1)
                return a;
        return -1;
    }
}

我的算法里面是判断出现N次，但是实际上，只要出现2次，则该数就是目标，因为2N个数=N+1的唯一和N个重复（这多了一个，是因为多的那个就是重复N次的）
两种算法的思路都是一样的。