题目
在一个长度为 n 的数组里的所有数字都在 0 到 n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字是重复的，也不知道每个数字重复几次。请找出数组中任意一个重复的数字。
Input:
{2, 3, 1, 0, 2, 5}
Output:
2
思路：
题目中的关键信息：
- 由于这个数组的长度为 n，而且里面所有的数字都在 0 到 n-1 的范围内。
- 只要求找出数组中任意一个重复的数字。
解法
我们有三种解法可以选择：
- 给数组进行排序，最好的时间复杂度就是O(nlogn)。
- 使用一个hashmap，只需要遍历一次添加到hashmap中，再以O(1)的时间复杂度拿到重复的数字。该算法时间复杂度为O(n)，空间复杂度为：O(n)。
- 使用题目中给出的关键信息来做（原因：由于所有的数子都在0 到 n-1 范围内，也就是该数组中所有的数字都能用数组的下标来进行表示 ），让数组中每一个数字都放在和该数字相等的数组下标。时间复杂度为O(n)，空间复杂度为O(1)。
例如：
// 扫描数组，并把对应的数字和该数字相等的数组下标位置的数字进行交换。
{2,3,0,1,4,3} // 数组下标0，数字2，和数组下标为2的数字（0），判断不相等，则进行交换，否则直接返回该数字。
{0,3,2,1,4,3} // 数组下标0，数字0，相等。扫描下一个数，下一个数数组下标1，数字3，和数组下标为3的数字 (4) 进行判断，不相等则交换。
{0,4,2,1,3,3} // 数组下标还是为1，数字4，和数组下标4的数字 (3) 进行判断，不相等则交换
{0,3,2,1,3,4} // 数组下标还是1，数字3，和数组下标3的数字（3）进行判断，相等，直接返回该数字。
代码
public class solution{
public int duplicate(int[] nums){
// 这里可以问一下面试官，要直接抛出异常还是返回 -1
if(nums == null || nums.length <= 0){
return -1;
}
for(int i = 0;i <nums.length;i++){
//这里要使用while
while(nums[i] != i){
if(nums[i] == nums[nums[i]]){
return nums[i];
}
swap(nums,i,nums[i]);
}
}
return -1;
}
private void swap(int[] nums,int i,int j){
int t = nums[i];
nums[i] = nums[j];
nums[j] = t;
}
}
