這是悅樂書的第365次更新，第393篇原創
01 看題和準備
今天介紹的是
LeetCode
算法題中
Easy
級别的第
227
題（順位題号是
961
）。在大小為
2N
的數組
A
中，存在
N+1
個唯一進制素，并且這些元素中的一個重複
N
次。
傳回重複N次的元素。例如：
輸入：[1,2,3,3]
輸出：3
輸入：[2,1,2,5,3,2]
輸出：2
輸入：[5,1,5,2,5,3,5,4]
輸出：5
注意：
- 4 <= A.length <= 10000
- 0 <= A [i] <10000
- A.length是偶數
02 第一種解法
題目的意思是找數組
A
中出現了
N/2
次的數，其中
N
為數組
A
的長度。使用
HashMap
，
key
為數組元素，
value
為其出現次數，先将
A
中的元素初始化進
HashMap
中，然後周遊
HashMap
，找到
value
等于
N/2
的
key
傳回即可。
public int repeatedNTimes(int[] A) {
Map<Integer, Integer> map = new HashMap<Integer, Integer>();
for (int n : A) {
map.put(n, map.getOrDefault(n, 0)+1);
}
int half = A.length/2;
for (Integer key : map.keySet()) {
if (map.get(key) == half) {
return key;
}
}
return -1;
}
03 第二種解法
同樣是先記數再查找的思路，将第一種解法的
HashMap
換成
int
數組，長度為10001，新數組count的索引為
A
中的元素，值為
A
中元素的出現次數，然後周遊
count
數組，傳回其中值等于
N/2
的索引，
N
A
的長度。
public int repeatedNTimes2(int[] A) {
int[] count = new int[10001];
for (int n : A) {
count[n]++;
}
int half = A.length/2;
for (int i=0; i<count.length; i++) {
if (count[i] == half) {
return i;
}
}
return -1;
}
04 第三種解法
換一種角度來看，把數組中的重複元素找到就行，而去重首選
HashSet
，周遊
A
中的元素，如果
HashSet
中已經存在目前元素，即此元素就是要找的多次出現的元素。
public int repeatedNTimes3(int[] A) {
Set<Integer> set = new HashSet<Integer>();
for (int n : A) {
if (set.contains(n)) {
return n;
} else {
set.add(n);
}
}
return -1;
}
05 第四種解法
和第三種解法的思路相同，隻是将
HashSet
換成了
int
數組。
public int repeatedNTimes4(int[] A) {
int[] count = new int[10001];
for (int n : A) {
if(++count[n] >= 2) {
return n;
}
}
return -1;
}
06 第五種解法
在第四種解法的基礎上，做進一步簡化，使用字元串代替。建立一個字元串str，如果目前元素沒有出現過在str中，就拼接到str上，反之就是str中已經存在了該元素，傳回該元素即可。
public int repeatedNTimes5(int[] A) {
String str = "";
for (int n : A) {
if (str.indexOf(n+"") < 0) {
str += n;
} else {
return n;
}
}
return -1;
}
07 第六種解法
直接使用兩層循環，比對相等的元素。
public int repeatedNTimes6(int[] A) {
int n = A.length;
for (int i=0; i<n; i++) {
for (int j=i+1; j<n; j++) {
if (A[i] == A[j]) {
return A[i];
}
}
}
return -1;
}
08 第七種解法
此解法來自
LeetCode
給的參答，這個思路很奇妙，算是在第六種解法基礎上的進一步簡化。
同樣使用兩層循環，但是不像第六種解法那樣每次都是比較相鄰的元素，而是分3次跳着比較，第一次是比較相鄰元素，第二次是比較間隔1位的元素，第三次是比較間隔2位的元素，将A切分成4個長度為一組的子數組，将其中的元素與其距離1、2、3的元素做比較，至少會存在一個重複元素在其中。
public int repeatedNTimes7(int[] A) {
int n = A.length;
for (int i=1; i<=3; i++) {
for (int j=0; j<n-i; j++) {
if (A[j] == A[j+i]) {
return A[i];
}
}
}
return -1;
}
09 小結
算法專題目前已連續日更超過七個月，算法題文章233+篇，公衆号對話框回複【資料結構與算法】、【算法】、【資料結構】中的任一關鍵詞，擷取系列文章合集。
以上就是全部内容，如果大家有什麼好的解法思路、建議或者其他問題，可以下方留言交流，點贊、留言、轉發就是對我最大的回報和支援！
![241 Different Ways to Add Parentheses（C代碼版）[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)