这是悦乐书的第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=)