在一個長度為n的數(shù)組里的所有數(shù)字都在0到n-1的范圍內(nèi)。 數(shù)組中某些數(shù)字是重復(fù)的，但不知道有幾個數(shù)字是重復(fù)的。也不知道每個數(shù)字重復(fù)幾次。請找出數(shù)組中任意一個重復(fù)的數(shù)字。
例如，如果輸入長度為7的數(shù)組{2,3,1,0,2,5,3}，那么對應(yīng)的輸出是第一個重復(fù)的數(shù)字2或者3。

思路：
1，利用哈希表進(jìn)行比較，containsKey(numbers[i])找出重復(fù)值
2，先排序，再按序兩兩比較
3，創(chuàng)建一個布爾型數(shù)組，遇到數(shù)組中的數(shù)，則將其下標(biāo)對應(yīng)位置值記錄為true，每次賦值前作出判斷是否重復(fù)
4，因為界限問題，掃描拿下標(biāo)和數(shù)組數(shù)字相比較，如果相等則繼續(xù)掃描，不相等則和對應(yīng)數(shù)字為下標(biāo)位置上的數(shù)相比較是否相等，相等則跳出，不相等則交換
5，因為范圍限定，使用二分查找，按照數(shù)據(jù)的范圍進(jìn)行二分，然后在數(shù)組中尋找對應(yīng)范圍的數(shù)據(jù)，與之間的個數(shù)進(jìn)行比較，大于必然重復(fù)。終止條件為end == start，判斷count不大于1則終止，否則也重復(fù)。 時間復(fù)雜度為o(n),空間復(fù)雜度為o(1)
代碼如下：

/**
     * 先排序，然后兩兩比較，時間復(fù)雜度為o(nlogn)
     * @param numbers
     * @param length
     * @return
     */

    public static ArrayList duplicate(int numbers[],int length) {
        if (numbers.length < 0 || numbers == null){
            return null;
        }
        Arrays.sort(numbers);
        int i;
        ArrayList list = new ArrayList();
        for(i=0;i<length-1;i++){
            if (numbers[i] == numbers[i+1]){
               list.add(numbers[i]);
            }
        }
        return list;
    }

    /**
     * 借用哈希表進(jìn)行解決，時間復(fù)雜度為O(n),需要一個哈希表空間復(fù)雜度為o(n)
     * @param numbers
     * @param len
     * @return
     */
    public static ArrayList duplicate2(int numbers[],int len){
        if (numbers.length < 0 || numbers == null){
            return null;
        }
        ArrayList list = new ArrayList();
        Map map = new HashMap<>();
        for (int i=0;i<len;i++){
            if (!map.containsKey(numbers[i])) {
                map.put(numbers[i], i);
            }else {
                list.add(numbers[i]);
            }
        }
        return list;
    }

    /**
     * 空間復(fù)雜度為O(1),循環(huán)數(shù)組，先跟自己下標(biāo)相比是否相等
     * 如果相等則繼續(xù)遍歷
     * 如果不相等則比較其值作為下標(biāo)對應(yīng)位置的值是否相等
     * 不相等則交換位置
     * 相等則退出
     * @param numbers
     * @param len
     * @return
     */
    public static ArrayList duplicate3(int numbers[],int len){
        if (numbers.length < 0 || numbers == null){
            return null;
        }
        for (int i = 0;i < len;i++){
            if (numbers[i] < 0 || numbers[i] > len -1) {
                return null;
            }
        }
        ArrayList list = new ArrayList();
        int i = 0;
        while (i < len){
            if (numbers[i] == i){
                i++;
            }else if (numbers[i] != numbers[numbers[i]]){
               swap(numbers[i],numbers[numbers[i]]);
            }else {
                list.add(numbers[i]);
                break;
            }
        }

        return list;
    }

    private static void swap(int a,int b) {
        int tepm = a;
        a = b;
        b = tepm;
    }
    /**
     * 雙重循環(huán)遍歷解決
     * @param numbers
     * @param length
     * @return
     */
    public static ArrayList duplicate1(int numbers[],int length) {
        if (numbers.length < 0 || numbers == null){
            return null;
        }
        int i,j;
        ArrayList list = new ArrayList();
        for (i=0;i<length-1;i++){
            for (j=i+1;j<length;j++)
              if (numbers[i] == numbers[j]){
                list.add(numbers[j]);
              }
        }
        return list;
    }
    /**
     * boolean只占一位，所以還是比較省的，利用數(shù)組下標(biāo)不重復(fù)，將數(shù)組內(nèi)數(shù)值變成布爾類型的下標(biāo)
     * 遇到下標(biāo)位置數(shù)值為true的則重復(fù),時間和空間復(fù)雜度和哈希類似
     */

    public boolean duplicate(int numbers[], int length, int[] duplication) {
        boolean[] k = new boolean[length];
        for (int i = 0; i < k.length; i++) {
            if (k[numbers[i]] == true) {
                duplication[0] = numbers[i];
                return true;
            }
            k[numbers[i]] = true;
        }
        return false;
    }