题目描述：
在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字2。
解法
1.排序法
对数组进行排序后，判断相邻两个元素是否相等，相等则返回
public boolean duplicate(int numbers[],int length,int [] duplication) {
//判断特殊情况
if(length==0){
duplication[0] = -1;
return false;
}
//排序
Arrays.sort(numbers);
//查找排序后的数组的相邻位置是否存在相同元素，存在则返回
for(int i=0;i<length-1;i++){
if(numbers[i]==numbers[i+1]){
duplication[0] = numbers[i];
return true;
}
}
duplication[0] = -1;
return false;
}
}
时间复杂度：O(nlogn)
空间复杂度：O(1)
2.利用HashSet辅助完成
新建一个HashSet，循环数组进行判断：
1）若HashSet中不存在当前元素，则将当前元素加到HashSet中
2）若HashSet中存在当前元素，则说明当前元素为重复元素
public class Solution {
// Parameters:
// numbers: an array of integers
// length: the length of array numbers
// duplication: (Output) the duplicated number in the array number,length of duplication array is 1,so using duplication[0] = ? in implementation;
// Here duplication like pointor in C/C++, duplication[0] equal *duplication in C/C++
// 这里要特别注意~返回任意重复的一个，赋值duplication[0]
// Return value: true if the input is valid, and there are some duplications in the array number
// otherwise false
public boolean duplicate(int numbers[],int length,int [] duplication) {
//判断特殊情况
if(length==0){
duplication[0] = -1;
return false;
}
//新建一个HashSet作为辅助
HashSet<Integer> hs = new HashSet<Integer>();
//循环数组进行判断：若HashSet中不存在当前元素，将当前元素添加到HashSet中；若存在，说明当前元素就是重复元素
for(int num:numbers){
if(!hs.contains(num)){
hs.add(num);
}
else{
duplication[0] = num;
return true;
}
}
duplication[0] = -1;
return false;
}
}
时间复杂度：O(n)
空间复杂度：O(n)
3.根据特性
数组的长度为 n 且所有数字都在 0 到 n-1 的范围内，我们可以将每次遇到的数进行"归位"，当某个数发现自己的"位置"被相同的数占了，则出现重复
public class Solution {
// Parameters:
// numbers: an array of integers
// length: the length of array numbers
// duplication: (Output) the duplicated number in the array number,length of duplication array is 1,so using duplication[0] = ? in implementation;
// Here duplication like pointor in C/C++, duplication[0] equal *duplication in C/C++
// 这里要特别注意~返回任意重复的一个，赋值duplication[0]
// Return value: true if the input is valid, and there are some duplications in the array number
// otherwise false
public boolean duplicate(int numbers[],int length,int [] duplication) {
//判断特殊情况
if(length==0){
duplication[0] = -1;
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;
}
else{
int tmp = numbers[i];
numbers[i] = numbers[tmp];
numbers[tmp] = tmp;
}
}
}
duplication[0] = -1;
return false;
}
}
时间复杂度：O(n)
空间复杂度：O(1)
