哈希set, 辅助数组下标, 交换法 , 排序法 四种方式
/*
找出数组中任意一个重复数字:
1.哈希set遍历数字,碰到第一个重复的就返回
2.创建一个对应大小的数组,数组的位置对应数字n, 遍历到该数组则arr[n]+1
若arr[n]>=2,则说明遇到重复的了,直接返回
3.交换法,因为数字都在0~n-1之间,所以我们直接把每个数字放到它对应下标的位置去:
num[i] = index;
若index==i,说明该位置放置正确,去下一个位置遍历
若index!=i,说明该位置错误,需要进行调换:
- 若 num[index] == index说明要交换的位置已存放好,即遇到了重复数字
- 否则 index放到它应该放的地方, 与index的位置的值进行交换,继续遍历判断i位置
4.排序法,先将数组排序,然后遍历到相邻元素一致则返回
*/
public int duplicate (int[] numbers) {
int temp;
int i=0;
while(i<numbers.length){
temp = numbers[i];
if(temp==i){ //位置正确,遍历下一个
i++;
}else{ //位置放置错误
if(numbers[temp]!=temp){ //a.且要交换的位置 并没有摆好
numbers[i] = numbers[temp]; //交换位置
numbers[temp] = temp; //把该位置放好
}else{ //b.要交换的位置已经摆好了,说明遇到重复元素
return temp;
}
}
}
return -1;
/*
int[] arr = new int[numbers.length];
int temp;
for(int i=0;i<numbers.length;i++){
temp = numbers[i]; //temp对应遍历到的数字,对应arr数组下标
if(arr[temp]==1){
return temp; //遇到重复数字
}
arr[temp]++; //遍历到temp,对应temp位置+1
}
return -1;
*/
/*
HashSet<Integer> set = new HashSet();
for(int i=0;i<numbers.length;i++){
if(!set.add(numbers[i])){
return numbers[i];
}
}
return -1;
*/
}