3. 数组中重复的数字

题目一

• 题目描述：

长度为n的数组，所有数字都在0~n-1内。找出数组中的重复数字。如入参{2,3,1,0,2,5,3}，对应重复数字为2或者3。

• 解题思路：

要求时间复杂度O(N)，空间复杂度O(1)。因此不能使用排序的方法，也不能使用额外的标记数组。

对于这种数组元素在[0, n-1]范围内的问题，可以将值为i的元素调整到第i个位置上进行求解。

以(2, 3, 1, 0, 2, 5)为例，遍历到位置4时，该位置上的数为2，但是第2个位置上已经有一个2的值了，因此可以知道2重复。

• 代码：

public static boolean findDuplicateNumber1(int[] array, int[] duplications) {
    if (array == null || array.length < 1) {
        return false;
    }
    int len = array.length;
    for (int i = 0; i < len; i++) {
        if (array[i] < 0 || array[i] > len) {
            return false;
        }
    }
    for (int i = 0; i < len; i++) {
        while (array[i] != i) {
            if (array[i] == array[array[i]]) {
                duplications[0] = array[i];
                return true;
            }
            int temp = array[i];
            array[i] = array[temp];
            array[temp] = temp;
        }
    }
    return false;
}

题目一

• 题目描述：长度为n+1的数组里，所有数字都在1~n的范围内，所以数组中至少有一个重复数字。请找出任意一个重复数字，但不能修改输入的数组。例如输入{2,3,5,4,3,2,6,7}，对应重复数字为2或者3。

• 解题思路： 不能修改原数组，可以引入一个长度为n的辅助数组，但是这样的话空间复杂度要求O(n)。

利用二分法的概念，以中间的数字m将1~n的分为1~m和m+1~n两部分，分别统计两个范围内的数字的个数，如果1~m的数字的数目超过m，则重复数字在m中；否则m+1~n的区间里一定包含重复数字。然后继续将m+1~n的区间拆分为两份，直到找到一个重复的数字。

如数组{2,3,5,4,3,2,6,7}，数字范围为1~7，分为1~4和5~7两段，1~4有5个，所以一定有重复数字；然后1~4分为1~2和3~4两段，1~2有2个，3~4有3个，所以3~4一定有重复数字；然后再分为3和4两段，3有两次，即3为重复数字。

• 代码：

public static int findDuplicateNumber2(int[] array) {
    if (array == null || array.length < 1) {
        return -1;
    }
    int start = 1;
    int end = array.length - 1;
    while (start <= end) {
        int mid = (end - start) / 2 + start;
        int count = countRange(array, start, mid); //统计范围内不同数字个数
        if (end == start) { //当只统计一个数字时，如果count>1就是重复数字
            if (count > 1) {
                return start;
            } else {
                break;
            }
        }
        if (count > (mid - start + 1)) {
            end = mid;
        } else {
            start = mid + 1;
        }
    }
    return -1;
}

private static int countRange(int[] array, int start, int end) {
    if (array == null) {
        return 0;
    }
    int count = 0;
    for (int i = 0; i < array.length; i++) {
        if (array[i] >= start && array[i] <= end) {
            count++;
        }
    }
    return count;
}