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唯一的數(shù)值肛跌，然后有一個數(shù)值重復(fù)N次
解題思路：
1、想把數(shù)組拆分長度為2的子集篙梢。某個子集會出現(xiàn)以下兩種情況
a光羞、該子集不包含該重復(fù)值，則必定有一個子集包含兩個穴豫，則i==i+1
b凡简、該子集包含該重復(fù)值，如果相鄰的子集不包含該值精肃，則會出現(xiàn)a情況秤涩。
響鈴有值，則只有存在以下情況： abad司抱、adba筐眷。則i==i+2和i==i+3情況。
