【劍指offer】面試題3：數組中重複的數字

題目

在一個長度為n的數組裡的所有數字都在0到n-1的範圍内。

數組中某些數字是重複的，但不知道有幾個數字是重複的。

也不知道每個數字重複幾次。請找出數組中任意一個重複的數字。

例如，如果輸入長度為7的數組{2,3,1,0,2,5,3}，那麼對應的輸出是第一個重複的數字2。

思路

解法1：

對數組排序，然後找出重複數字

時間複雜度O(nlogn)

空間複雜度O(1)

解法2：

使用哈希表

時間複雜度O(n)

空間複雜度O(n)

注意題目中的一個條件：所有數字都在0到n-1的範圍内

解法1和解法2都是最普通的做法，并沒有利用好這個條件。

解法3：

周遊數組，當周遊到下标為i的數字時，首先比較arr[i]是否等于i

如果arr[i]等于i，則周遊下一個數字；

如果arr[i]不等于i，且arr[arr[i]]不等于arr[i]，則交換這兩個元素的值；

如果arr[i]不等于i，且arr[arr[i]]等于arr[i]，則該元素為重複數字

例如：

數組{2,3,1,0,2,5,3}

1.arr[0]等于2≠0，且arr[2]不等于2，則交換元素，數組變成{1,3,2,0,2,5,3}

2.arr[0]等于1≠0，且arr[1]不等于1，則交換元素，數組變成{3,1,2,0,2,5,3}

3.arr[0]等于3≠0，且arr[3]不等于3，則交換元素，數組變成{0,1,2,3,2,5,3}

4.arr[0]等于0

5.arr[1]等于1

6.arr[2]等于2

7.arr[3]等于3

8.arr[4]等于2≠4，且arr[2]等于2，則找到重複元素2

代碼

public class _03_DuplicationInArray {

    // 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 static boolean duplicate(int numbers[],int length,int [] duplication) {
        if(numbers == null || numbers.length <  || length <  || 
                duplication == null || duplication.length == )
            return false;
        boolean hasDuplicate = false;
        int i = ;
        while(i < length) {
            int m = numbers[i];
            if(m == i) {
                ++i;
            }
            else if(numbers[m] != m) {
                numbers[i] = numbers[m];
                numbers[m] = m;
            }
            // 找到了重複元素
            else {
                hasDuplicate = true;
                duplication[] = m;
                break;
            }
        }
        return hasDuplicate;
    }
}
           

測試

public class _03_Test {

    public static void main(String[] args) {
        test1();
        test2();
        test3();
    }

    private static void test1() {
        int[] duplication = new int[];
        boolean b = _03_DuplicationInArray.duplicate(new int[] {,,,,,,}, , duplication);
        MyTest.equal(b, true);
        System.out.println(duplication[]);

        b = _03_DuplicationInArray.duplicate(new int[] {,,,,}, , duplication);
        MyTest.equal(b, false);
    }

    private static void test2() {
        int[] duplication = new int[];
        boolean b = _03_DuplicationInArray.duplicate(new int[] {,}, , duplication);
        MyTest.equal(b, false);

        b = _03_DuplicationInArray.duplicate(new int[] {,}, , duplication);
        MyTest.equal(b, true);
        System.out.println(duplication[]);
    }

    private static void test3() {
        int[] duplication = new int[];
        boolean b = _03_DuplicationInArray.duplicate(null, , duplication);
        MyTest.equal(b, false);

        b = _03_DuplicationInArray.duplicate(new int[] {}, , duplication);
        MyTest.equal(b, false);

        b = _03_DuplicationInArray.duplicate(new int[], , duplication);
        MyTest.equal(b, false);
    }
}