备忘录
- 开辟新空间,值为n的存在下标为n+1的位置
- 要开辟额外空间
public boolean duplicate(int numbers[],int length,int [] duplication) {
if(numbers == null) {
return false;
}
int[] cache = new int[length];
// 备忘录记录
for(int num : numbers) {
if(cache[num] == 0) {
cache[num] = 1;
} else {
duplication[0] = num;
return true;
}
}
return false;
}
交换法
- 从第一个开始,该值和下标不同就交换,相同就下一个,直到走完
- 不能保证找出第一个最小值
public boolean duplicate(int numbers[],int length,int [] duplication) {
if(numbers == null) {
return false;
}
int i = 0;
while(i < length) {
if(numbers[numbers[i]] != numbers[i]) {
int temp = numbers[numbers[i]];
numbers[numbers[i]] = numbers[i];
numbers[i] = temp;
} else if(i == numbers[i]){
i++;
} else {
duplication[0] = numbers[i];
return true;
}
}
return false;
}