剑指offer——面试题3_2：不修改数组找出重复的数字

1.题目描述：

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

2.解题思路：

可以利用二分查找的思想来找出重复的数字：把从1 ~ n 的数字从它们所处范围的中间数字 m 分为两部分：1 ~ m 和 m+1 ~ n。如果 1 ~ m 的数字的个数大于 m，那其中一定有重复数字。否则，另一半 m+1 ~ n 里就一定有重复数字。可以重复这个过程，直到找到一个重复数字。

3.代码实现：

public class Offer_3 {
    public static void main(String[] args) {
        int[] array = {2, 3, 5, 4, 3, 2, 6, 7};
        System.out.println(duplicate(array));
    }
    public static int duplicate(int[] array) {
        //判空
        if (array == null || array.length == 0) {
            return -1;
        }
        //判断是否所有数字都在1~n的范围内
        for (int i = 0; i < array.length; i++) {
            if (array[i] < 1 || array[i] > array.length - 1) {
                return -1;
            }
        }
        int start = 1;
        int end = array.length - 1;
        while (end >= start) {
            //计算中间数
            int middle = (end - start) / 2 + start;
            //统计1~n在array[start]~array[middle]中出现的次数
            int count = countRange(array, start, middle);
            //如果上下限一致，说明已经判断到最中间的数字了，此时判断count的个数，大于1则说明是重复数字,否则说明没有重复数字，直接返回-1
            if (end == start) {
                if (count > 1) {
                    return end;
                } else {
                    return -1;
                }
            }
            //如果count大于区间长度，说明有重复数字，否则，就在另一个区间内
            if (count > (middle - start + 1)) {
                end = middle;
            } else {
                start = middle + 1;
            }
        }
        //走到这说明没有重复数字
        return -1;
    }

    private static int countRange(int[] array, int start, int end) {
        if (array == null || array.length == 0) {
            return 0;
        }
        int count = 0;
        // 对数组中的所有数字，统计在区间内的个数
        for (int i = 0; i < array.length; i++) {
            if (array[i] >= start && array[i] <= end) {
                count++;
            }
        }
        return count;
    }
}

复杂度分析：

• 时间复杂度：O(n)，对于输入长度为n的数组，函数countRnage将被调用O(logn)次，每次需要O(n)的时间，所以总的时间复杂度为O(nlogn).
• 空间复杂度：O(1)，不需要额外开辟新的空间。