題目:
在一個長度為 n 的數(shù)組里的所有數(shù)字都在0 到 n-1 的范圍內(nèi)。數(shù)組中某些數(shù)字是重復的定踱，但不知道有幾個數(shù)字是重復的颜说，也不知道每個數(shù)字重復幾次。請找出數(shù)組中任意一個重復的數(shù)字荆隘。
Input:
{2, 3, 1, 0, 2, 5}
Output:
2
思路:
1.排序:O(nlogn)
2.放進hashmap: 時間O(n) 空間O(n)
3.根據(jù)0-n-1這個條件,將值為 i 的元素調(diào)整到第 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];
}
}
