题目：
在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字2。
Input:
{2,3,1,0,2,5,3}
output:
2
题目大意：
题目很清晰，找出数组中任意一个重复的数字。其中数组长度为n，数组元素在[0,n-1]内。其实本题就是找到了第一个重复的数字，若找其后的重复位置，加一个计数器，并修改一下if的判别条件，很容易做到。
解题思路：
首先，数组长度规定为n，且所有数字都在0到n-1的确定范围内。可以用Hash的思想。
不知道为什么想到了桶排序。若用到排序，时间复杂度至少就是O(nlogn)。
其次，很容易想到暴力求解，两次扫描数组的方法，时间复杂度为O(n^2)。
最后，如果要使用时间复杂度为O(n)的算法，就需要利用Hash表来对已有数据进行存储。或者将值为i的元素调整到第i个位置上，
代码：
使用哈希的思想，Java语言使用HashSet这个容器，时间复杂度O(n)，空间复杂度O(n)。利用 HashSet 解决，从头到尾扫描数组，每次扫描到一个数，判断当前数是否存在 HashSet 中，如果存在，则重复，对 duplication 赋值返回，否则将该数加入到 HashSet 中1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 public boolean duplicate(int numbers[],int length,int [] duplication) {
if(numbers == null || numbers.length == 0) return false;
Set<Integer> set = new HashSet<>();
int ith = 0;
for(int i = 0 ;i < length;i++){
if(set.contains(numbers[i]) && ith == 0){ ## ith == 第几个重复的数字
duplication[ith++] = numbers[i];
return true;
}
else{
set.add(numbers[i]);
}
}
return false;
}
}
还有一种时间复杂度为O(n^2)(我认为是n^2的复杂度，CyC2018这个学长写n的复杂度应该是错了吧。。),空间复杂度为O(1)的方法，并不用额外的哈希数组,但是需要调整一下原先的数组。将值为i的元素调整到第i个位置上，如果第i个位置上已经有一个i的元素，则证明i值重复。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24Java:
public boolean duplicate(int numbers[],int length,int [] duplication) {
if(numbers == null || length <= 0) return false;
int ith = 0;
for(int i = 0;i < length;i++){
while(numbers[i] != i ){
if(numbers[i] == numbers[numbers[i]] && ith == 0){
duplication[ith++] = numbers[i];
return true;
}
swap(numbers,i,numbers[i]);
}
}
return false;
}
private void swap(int[] nums,int i,int j){
int t = nums[i];
nums[i] = nums[j];
nums[j] = t;
}
python:
