題目：在一個長度為n的數(shù)組里的所有數(shù)字都在0到n-1的范圍內(nèi)。數(shù)組中某些數(shù)字是重復(fù)的，但不知道有幾個數(shù)字重復(fù)了，也不知道每個數(shù)字重復(fù)的次數(shù)。請找出數(shù)組中任意一個重復(fù)的數(shù)字。

思路：

1、首先想到的是排序，然后再做處理；
2、利用哈希表，數(shù)組中值作為key，出現(xiàn)次數(shù)作為value（當(dāng)然此處也可用數(shù)組代替哈希表），構(gòu)造完哈希表后，查詢value大于1的key，空間復(fù)雜度O(n)，時間復(fù)雜度O(n);
3、不使用額外的空間，將數(shù)組中值為i的元素?fù)Q到i位置

舉個例子

arr={2,3,1,0,2,5}
輸出為：2
index：0  （2，3，1，0，2，5）2與1交換
          （1，3，2，0，2，5）1與3交換
          （3，1，2，0，2，5）3與0交換
          （0，1，2，3，2，5）0處于index=0的位置
          （0，1，2，3，2，5）1處于index=1的位置
           ......
遍歷到index=4時，會發(fā)現(xiàn)index=2位置上已經(jīng)有2了，故2重復(fù)了。

方法三的java代碼如下

public class code_2_solution {
    /***
     * 查找數(shù)組中重復(fù)的數(shù)字
     * @param arr
     * @return
     */
    public static int findDuplicateNum(int[] arr) {
        int res= Integer.MAX_VALUE;
        if(arr==null || arr.length==0) return res; 
        for (int i=0;i<arr.length;i++) {
            while(arr[i] !=i) {
                if (arr[i]==arr[arr[i]]) {
                    res = arr[i];
                    break;
                }
                swapNum(arr,i);

            }
        }
        return res;
    }

    public static void swapNum(int[] arr, int index){
        int temp = arr[index];
        arr[index] = arr[temp];
        arr[temp] = temp;
    }
    
}

難免紕漏，歡迎指正。