题解 | #数组中重复的数字#
数组中重复的数字
http://www.nowcoder.com/practice/6fe361ede7e54db1b84adc81d09d8524
参考:
//解题思路
/*替换法(O(n),O(1))
数组存放原则:numbers[i] = i
遍历数组所有元素,交换不符合数组存放原则的元素:
例如[2,3,1,0,2]
遍历0位元素2:(交换0位元素2和2位元素1)->[1,3,2,0,2]
遍历0位元素1:(交换0位元素1和1位元素3)->[3,1,2,0,2]
遍历0位元素3:(交换0位元素3和3位元素0)->[0,1,2,3,2]
依次遍历0、1、2、3位置元素,都符合存放原则numbers[i] = i,不做任何操作
遍历末位元素2,此时末位元素2和2位元素2相等,出现了两次,即数字2位重复元素
*/
public int duplicate (int[] numbers) {
for (int i = 0; i < numbers.length; i++) {
if (numbers[i] != i){
if (numbers[i] == numbers[numbers[i]]) return numbers[i];
int temp = numbers[numbers[i]];
numbers[numbers[i]] = numbers[i];
numbers[i] = temp;
i--;//遍历完0位元素以及交换完数字后,如果0位元素仍不符合数组存放原则:numbers[i] = i,那么还要重新遍历0位元素
}
}
return -1;
}
自己写的:
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
*
* @param numbers int整型一维数组
* @return int整型
*/
public int duplicate (int[] numbers) {
// write code here
int[] count_numbers = new int[numbers.length];
for(int i = 0; i < count_numbers.length; i++){
count_numbers[i] = 0;
}
for(int i = 0; i < numbers.length; i++){
count_numbers[numbers[i]] = count_numbers[numbers[i]] + 1;
if (count_numbers[numbers[i]] == 2){
return numbers[i];
}
}
return -1;
}
}