题目:
在一个长度为 n 的数组里的所有数字都在0 到 n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字是重复的，也不知道每个数字重复几次。请找出数组中任意一个重复的数字。
Input:
{2, 3, 1, 0, 2, 5}
Output:
2
思路:
1.排序:O(nlogn)
2.放进hashmap: 时间O(n) 空间O(n)
3.根据0-n-1这个条件,将值为 i 的元素调整到第 i 个位置上。向后遍历
时间O(n),空间O(1)
public class RapetNum {
public boolean duplicate(int numbers[],int length,int [] duplication) {
if(numbers == null || numbers.length <= 0) {
return false;
}
for(int i = 0; i < length; i++) {
while(i != numbers[i]) {
if(numbers[i] == numbers[numbers[i]]){
duplication[0] = numbers[i];
return true;
}
swap(numbers,i,numbers[i]);
}
}
return false;
}
private void swap(int[] numbers, int i, int j) {
numbers[i] = numbers[i]^numbers[j];
numbers[j] = numbers[i]^numbers[j];
numbers[i] = numbers[i]^numbers[j];
}
}
