题解 | #数组中重复的数字#
数组中重复的数字
http://www.nowcoder.com/practice/6fe361ede7e54db1b84adc81d09d8524
1.思路是，既然题目规定所有数字都在0到n-1的范围内，那其实可以用类似位图的思路来解决。
拿到number[i]之后，去检查对应位图下标的位置是否为0，为0则设置为1，否则直接返回。
例如number[2] == 15，那就检查dp[15] == 1 ？ return 15 : dp[15] = 1
public int duplicate (int[] numbers) {
// write code here
int dp[] = new int[numbers.length];
for (int i = 0; i < numbers.length; i++) {
if (dp[numbers[i]] == 0) {
dp[numbers[i]] = 1;
} else {
return numbers[i];
}
}
return -1;
}
public int duplicate (int[] numbers) {
// write code here
HashSet set = new HashSet(numbers.length);
for(int i = 0; i < numbers.length; i++){
if(!set.add(numbers[i])){
return numbers[i];
}
}
return -1;
}
查看13道真题和解析