题目描述：

在一个长度为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)