剑指offer——面试题3_1：数组中重复的数字

1.题目描述：

在一个长度为 n 的数组里的所有数字都在 0 ~ n - 1的范围内。请找出任意一个重复的数字。
例如输入长度为7的数组 {2, 3, 1, 0, 2, 5, 3}，那么对应的输出是重复的数字2或者3。

2.解题思路：

可以利用计数排序的思想来找出重复的数字：把每个数字都交换到以它为索引的位置，其他位置再出现就表明它是重复数字。

从头到尾扫描数组（用array表示），当扫描到下标为 i 的数字 m （即 array[i] ）时，进行以下的步骤：
（1）比较 i 和 m 的值，若相等，说明 m 已经放在正确的位置，则继续往下扫描。
（2）如果 i 和 m 不相等，则将 m 和它本应该在的位置上的数 array[m] 进行比较，若相等，说明 m 在两个地方出现了，即为一个重复数字。
（3）如果 m 和 array[m] 不相等，则将 m 和 array[m] 交换，将 m 放在正确的位置，重新再对交换过来的 array[m] 的值进行判断。

3.代码实现：

public class Offer_3 {
    public static void main(String[] args) {
        int[] array = {2, 3, 1, 0, 2, 5, 3};
        duplicate(array);
    }
    public static void duplicate(int[] array) {
        //判空
        if (array == null || array.length == 0) {
            return;
        }
        //判断是否所有数字都在 0 ~ n - 1的范围内
        for (int i = 0; i < array.length; i++) {
            if (array[i] < 0 || array[i] > array.length - 1) {
                return;
            }
        }
        //遍历数组
        for (int i = 0; i < array.length; i++) {
            while (array[i] != i) {
                //第1步判断i与m是否相等，相等则直接进行下一次循环判断下一个数字
                if (array[i] == array[array[i]]) {
                    //第2步判断m与array[m]是否相等，相等则说明m为重复数字
                    System.out.println(array[i]);
                    return;
                } else {
                    //第3步先交换m和array[m]，再对array[m]进行判断
                    swap(array, array[i], array[array[i]]);
                }
            }
        }
    }
    public static void swap(int[] array, int a, int b) {
        int temp = 0;
        temp = array[a];
        array[a] = array[b];
        array[b] = temp;
    }
}

复杂度分析：

• 时间复杂度：O(n)，虽然有一个两重循环，但是事实上每个数字至多交换两次就可以放到正确的位置，因此总的时间复杂度是O(n)。
• 空间复杂度：O(1)，所有的操作都是在数组内进行交换，不需要额外开辟新的空间。