解法一: HashSet
import java.util.*;
public class Solution {
public boolean duplicate(int numbers[],int length,int [] duplication) {
duplication[0]=-1;
if(numbers==null||numbers.length==0) return false;
Set<Integer> set=new HashSet<>();
for(int i=0; i<numbers.length; i++){
if(!set.contains(numbers[i]))
set.add(numbers[i]);
else{
duplication[0]=numbers[i];
break;
}
}
return (duplication[0]!=-1);
}
}
解法二:in-place算法
public class Solution {
public boolean duplicate(int numbers[],int length,int [] duplication) {
duplication[0]=-1;
for(int i=0; i<length; i++){
while(numbers[i]!=i&&numbers[i]!=numbers[numbers[i]]){
int t=numbers[i];
int s=numbers[t];
numbers[t]=t;
numbers[i]=s;
}
}
for(int i=0; i<length; i++){
if(numbers[i]!=i){
duplication[0]=numbers[i]; return true;
}
}
return false;
}
}