數(shù)組中重復(fù)的數(shù)字

題目：在一個長度為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。

題目分析

解決這個問題的一個簡單的方法是先把輸入的數(shù)組排序。從排序的數(shù)組中找出重復(fù)的數(shù)字時間很容易的事情，只需要從頭到尾掃描排序后的數(shù)組就可以了。排序一個長度為 n 的數(shù)組需要 O(nlogn)的時間。

還可以利用哈希表來解決這個問題。從頭到尾按順序掃描數(shù)組的每個數(shù)，每掃描一個數(shù)字的時候，都可以用 O(1)的時間來判斷哈希表里是否已經(jīng)包含了該數(shù)字。如果哈希表里還沒有這個數(shù)字，就把它加入到哈希表里。如果哈希表里已經(jīng)存在該數(shù)字了，那么就找到一個重復(fù)的數(shù)字。這個算法的時間復(fù)雜度是 O(n)，但它提高時間效率是以一個大小為 O(n)的哈希表為代價的。我們再看看有沒有空間復(fù)雜度為 O(1)的算法。

我們注意到數(shù)組中的數(shù)字都在 0 到 n-1 中。如果這個數(shù)組中沒有重復(fù)的數(shù)字，那么當(dāng)數(shù)組排序之后數(shù)字 i 將出現(xiàn)在下標(biāo)為 i 的位置。由于數(shù)組中有重復(fù)的數(shù)字，有些位置可能存在多個數(shù)字，同時有些位置可能沒有數(shù)字。

現(xiàn)在讓我們重排這個數(shù)組，依然從頭到尾一次掃描這個數(shù)組中的每個數(shù)字。當(dāng)掃描到下標(biāo)為 i 的數(shù)字時，首先比較這個數(shù)字（用 m 表示）是不是等于 i。如果是，接著掃描下一個數(shù)字。如果不是，再拿它和第 m 個數(shù)字進(jìn)行比較。 如果它和第m個數(shù)字相等，就找到了一個重復(fù)的數(shù)字（該數(shù)字在下標(biāo)為 i 和 m 的位置都出現(xiàn)了）。如果它和第 m 個數(shù)字不相等，就把第 i 個數(shù)字和第 m 個數(shù)字交換，把 m 放到屬于它的位置。接下來再重讀這個比較、交換的過程，直到我們發(fā)現(xiàn)一個重復(fù)的數(shù)字。

以數(shù)組{2,3,1,0,2,5,3}為例來分析找到重復(fù)數(shù)字的步驟。數(shù)組的第 0 個數(shù)字（從 0 開始計(jì)數(shù)，和數(shù)組的下標(biāo)保持一致）是 2，與它的下標(biāo)不相等，于是把它和下標(biāo)為 2 的數(shù)字 1 交換。交換之后的數(shù)組是{1.3.2.0.2.5.3}。此時第 0 個數(shù)字是 1，仍然與它的下標(biāo)不相等，繼續(xù)把它和下標(biāo)為 1 的數(shù)字 3 交換，得到數(shù)組{3,1,2,0,2,5,3}.接下來繼續(xù)交換第 0 個數(shù)字 3 和第 3 個數(shù)字 0，得到數(shù)組{0,1,2,3,2,5,3}。此時第 0 個數(shù)字的數(shù)值為 0，接著掃描下一個數(shù)字。在接下來的幾個數(shù)字中，下標(biāo)為 1，2，3 的三個數(shù)字分別為 1，2，3 它們的下標(biāo)和數(shù)值都分別相等，因此不需要做任何操作。接下來掃描到下標(biāo)為 4 的數(shù)字 2。由于它的數(shù)值與它的下標(biāo)不相等，再比較它和下標(biāo)為 2 的數(shù)字。注意到此時數(shù)組中下標(biāo)為 2 的數(shù)字也是 2，也就是數(shù)字在下標(biāo)為 2 和下標(biāo)為 4 的兩個位置都出現(xiàn)了，因此找到一個重復(fù)的數(shù)字。

代碼實(shí)現(xiàn)

public class Test51 {
    /**
     * 題目：在一個長度為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或者。
     *
     * @param number
     * @return
     */
    public static int duplicate(int[] number) {
        if (number == null || number.length < 1) {
            return -1;
        }
        // 判斷輸入的是否在[0, number.length-1]之間
        for (int i : number) {
            if (i < 0 || i >= number.length) {
                return -1;
            }
        }
        for (int i = 0; i < number.length; i++) {
            // 當(dāng)number[i]與i不相同的時候一直交換
            while (number[i] != i) {
                // 如果i位置與number[i]位置的數(shù)字相同，說明有重復(fù)數(shù)字
                if (number[i] == number[number[i]]) {
                    return number[i];
                }
                // 如果不同就交換
                else {
                    swap(number, i, number[i]);
                }
            }
        }
        return -1;
    }
    private static void swap(int[] data, int x, int y) {
        int tmp = data[x];
        data[x] = data[y];
        data[y] = tmp;
    }
    public static void main(String[] args) {
        int[] numbers1 = {2, 1, 3, 1, 4};
        System.out.println(duplicate(numbers1));
        int[] numbers2 = {2, 4, 3, 1, 4};
        System.out.println(duplicate(numbers2));
        int[] numbers3 = {2, 4, 2, 1, 4};
        System.out.println(duplicate(numbers3));
        int[] numbers4 = {2, 1, 3, 0, 4};
        System.out.println(duplicate(numbers4));
        int[] numbers5 = {2, 1, 3, 5, 4};
        System.out.println(duplicate(numbers5));
    }
}

運(yùn)行結(jié)果

http://wiki.jikexueyuan.com/project/for-offer/images/69.png" alt="" />