算法：数组中重复的数字

题目描述

在一个长度为 n 的数组里的所有数字都在 0 到 n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字是重
复的，也不知道每个数字重复几次。请找出数组中任意一个重复的数字。

解题思路

这道题我在第一次做的时候，首先想到的就是利用hashset来直接寻找重复的数字。但是这肯定不是最好的方法。

题目中有一个关键的信息，所有数字都在 0 到 n-1 的范围内而数组的下标的取值访问也是0到n-1，那么我们就可以直接将所有数字映射到原数组中。在映射的过程中，判断是否有重复的即可。

以数组(2, 3, 1, 0, 2, 5) 为例，当我们遍历到index=4处，该位置上的数为2，应该放到数组下标为2的位置上去，但是该位置已经有一个2了，那么我们就可以断定2就是重复的。

解题代码

下面就是利用第二种解法，它的时间复杂度为O(N)，空间复杂度为O(1).

/**
 * 
 * @param numbers
 * @param length
 * @param duplication 在duplication[0]存放重复的数字
 * @return 存在重复的数字返回true，否则反之
 */
public boolean duplicate(int numbers[],int length,int [] duplication) {
    if(numbers==null||length<=0){
        return false;
    }
    for(int i=0;i<numbers.length;i++){
        while (numbers[i]!=i){
            if(numbers[i]==numbers[numbers[i]]){
                duplication[0]=numbers[i];
                return true;
            }
            //把numbers[i]移动到下标为numbers[i]的位置上
            swap(numbers,i,numbers[i]);
        }

    }
    return false;


}

private void swap(int[] arr,int a,int b){
    int tmp=arr[a];
    arr[a]=arr[b];
    arr[b]=tmp;
}