题目一：找出数组中重复的数字

在一个长度为n的数组里的所有数字都在0~n-1的范围内，数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。例如：如果长度为7的数组{2，3，1，0，2，5，3}，那么对应输出是重复的数字2或者3。

解法一：排序

排序后找出重复的数字就只需要从头到尾遍历即可。时间复杂度为：O(nlogn)

解法二：利用哈希表

从头到尾扫数组，每扫一个都可以用O(1)的时间来判断哈希表里是否存在相同元素，没有就将其放入哈希表，存在则为一个重复数字。时间复杂度为O(N)但是代价是哈希表的空间复杂度O(N).

解法三：下标判重

数组中的数字都在0~n-1之间，如果这个数组中不存在重复的数字，那么当数组排序后，数字i就在下标为i的位置。现在是存在重复的数字，那么一个下标则可能有多个数字。

步骤分析：

以{2，3，1，0，2，5，3}为例，下标0为2，将其与下标2的数字交换，则变为{1，3，2，0，2，5，3}。此时下标0为1，也不符，则与下标1的数字交换，则为{3，1，2，0，2，5，3}，按这个思路继续，直到变为{0，1，2，3，2，5，3}时，扫描到下标4，会发现其值2已经在之前交换过，此时则为重复元素。

代码：

class A {
    public static void main(String[] args) {
        int[] numbers = {2, 3, 1, 0, 2, 5, 3};
        boolean duplicate = duplicate(numbers);
        System.out.println("is duplicate:"+duplicate);
    }

    private static boolean duplicate(int[] numbers) {
        if (numbers == null || numbers.length <= 0) {
            return false;
        }
        for (int number : numbers) {
            if (number < 0 || number > numbers.length - 1) {
                return false;
            }
        }
        //以上为判断数组是否合法 以下为主要逻辑
        for (int i = 0; i < numbers.length; i++) {
            //交换到numbers[i]==i才停止 停止后 for循环 i+1
            while (numbers[i] != i) {
                //这个条件可能不太好理解 但是你将上述文字读一遍 然后将i=4带入这个表达式就好理解了
                if (numbers[i] == numbers[numbers[i]]) {
                    //重复
                    System.out.println(numbers[i]);
                    return true;
                }
                //如果不相等 则number[i]与numbers[numbers[i]]交换元素
                int temp = numbers[i];
                numbers[i] = numbers[temp];
                numbers[temp] = temp;

            }
        }
        return false;
    }
}

这里需要一提的是，代码中尽管有一个双重循环，但是元素交换实际上只要2次，所以最终的时间复杂度为O(N)，然后操作都在输入数组上进行，不需要额外内存，空间复杂度为O(1).

题目二：不修改数组找出重复的数字

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

解法一：利用上一题的思路，我们创建一个新的n+1的辅助数组，然后逐一赋值到辅助数组对应下标的位置，比如第一个元素值为3，则复制到新数组的下标为3的地方，这样很容易就可以找到重复元素，但是需要O(N)的辅助空间。

解法二：尝试避免使用辅助空间。假象若没有重复的数字，那么从1~n就只有n个数字，如果取中心点m，分为1~m，与m+1到n，如果1~m的数字出现的次数超过了m，那么这里就一定有重复的数字，若无则考虑m+1~n，若有，再从中间分，依次循环。多思考下上面这句话，相信你可以理解。

以长度8的数组{2，3，5，4，3，2，6，7}，根据题目要求，这个长度为8的所有数字都在1~7，中间数字是4，将这组数字分为1~4和5~7，接下来统计下1~4这几个数字在数组中出现的次数，1为0次，2为2次，3为2次，4为1次，共5次，所以这里面一定有重复数字。接下来，再分为1~2，3~4两段，数字1为0次，2为2次，共2次，数字3为2次，4为1次，共3次，则3~4则一定存在重复，接着二分为3和4按以上规律。可以得知3为重复。但是这个解法有一个问题，就是并不能准确的知道哪个是重复数字，也就是说无法找出所有重复的数字，比如说上面遗漏的数字2。这里就没有所谓的最佳解法了，按需判断即可。

代码：

class B {

    public static void main(String[] args) {

        int[] numbers = {2, 3, 5, 4, 3, 2, 6, 7};
        int duplicate = getDuplicate(numbers);
        System.out.println(duplicate);
    }

    private static int getDuplicate(int[] numbers) {
        if (numbers == null || numbers.length <= 0) {
            return -1;
        }
        int start = 1;
        int end = numbers.length - 1;
        while (end >= start) {
            //位运算 防止有人看不懂  >> 1右移运算 相当于除2
            int middle = ((end - start) >> 1) + start;
            int middle2 = ((end - start) / 2) + start;
            System.out.println("mid " + middle + " mid2: " + middle2);

            int count = countRange(numbers, start, middle);
            if (end == start) {
                //分到最后一组 大于1则为重复 否则没有重复
                if (count > 1) {
                    return start;
                } else {
                    break;
                }
            }
            if (count > (middle - start) + 1) {
                //前半组 存在重复
                end = middle;
            } else {
                //后半组存在重复
                start = middle + 1;
            }
        }
        return -1;
    }

    /**
     * 计算该区间内数字出现的次数总和
     *
     * @param numbers 数组
     * @param start   区间起始点
     * @param end     区间结束点
     * @return 数字出现的总和
     */
    private static int countRange(int[] numbers, int start, int end) {
        if (numbers == null) {
            return 0;
        }
        int count = 0;
        for (int number : numbers) {
            //如果该数字在区间内 计数+1
            if (number >= start && number <= end) {
                ++count;
            }
        }
        return count;
    }

}

上述解法类似二分查找，如果长度为n，则countRange的调用次数为O(logn)，每次需要O(n)，时间复杂度为O(nlogn)，空间为O(1)。为时间换空间。

— 本题来自《剑指Offer》，仅作为自己加深印象与理解而写，书中为C++或C#，我从事Android，习惯Java，若有问题还请指出，感激不尽。