一、题目
在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字2。
二、思路
解法一：采用LinkedHashMap的解法
解法二：详见代码（推荐）
三、代码
解法一：
package cn1; import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Set; public class Solution {
public boolean duplicate(int numbers[],int length,int [] duplication) {
boolean flag=false; if(numbers==null||length==0){
return flag;
} //统计字符串的个数，注意用LinkedHashMap
LinkedHashMap<Integer, Integer> lhm = new LinkedHashMap<Integer, Integer>();
for (int num :numbers) {
if (lhm.containsKey(num)) {
lhm.put(num, lhm.get(num) + 1);
} else {
lhm.put(num, 1);
}
} //遍历map,寻找第一个只出现一次的数
int val= -1; Set<Map.Entry< Integer, Integer>> set = lhm.entrySet();
for (Map.Entry< Integer, Integer> es : set) {
int key = es.getKey();
int value = es.getValue();
if (value >= 2) {
val= key;
break;
}
} if(val!=-1){
duplication[0]=val;
flag=true;
} //返回结果
return flag;
}
}
解法二：
public boolean duplicate(int numbers[], int length, int[] duplication) {
boolean[] k = new boolean[length];
for (int i = 0; i < k.length; i++) {
if (k[numbers[i]] == true) {
duplication[0] = numbers[i];
return true;
}
k[numbers[i]] = true;
}
return false;
}
---------------------------------------------
参考链接：
https://www.nowcoder.com/questionTerminal/623a5ac0ea5b4e5f95552655361ae0a8