题解 | #数组中重复的数字#
数组中重复的数字
http://www.nowcoder.com/practice/6fe361ede7e54db1b84adc81d09d8524
这道题的关键在于时间复杂度要求为O(n),因此如果采用每一个元素都遍历一遍数组的话,时间复杂都就成了O(n^2)。 因此我们需要另辟蹊径,让数组中的每个元素都有一个状态(为 0 为没有遍历过,为 1 则为已被遍历过)。由于 0 <= n <= 10000,所以需要 new 一个大小为 10000 的整型数组 array 。当一个数 nums[ i ] 被遍历到时,将会把 array[ nums[ i ] ] 的值置为 1 来表示这个数已被遍历过一次了,当再次遍历到 nums[ i ] 时,就说明重复了,直接把值放回。这样时间复杂度就下降到了 O(n)。
public int duplicate (int[] numbers) {
int[] array = new int[10000];
for (int i = 0; i < numbers.length; i++) {
if (array[numbers[i]] == 0) {
array[numbers[i]] = 1;
}else {
return numbers[i];
}
}
return -1;
}