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

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

考虑如果没有数组中没有重复的数字，那么排序后会有arr[i] = i(因为元素在 0~n-1 的范围内)，那么现在我们遍历数组，让第i个位置的元素的值为i(从0开始)，做法是当arr[i] != i的时候，与第arr[i]的位置进行交换，这样可以使得第arr[i]个位置上的数是arr[i]，即arr[arr[i]] = arr[i]

int temp = arr[i];
arr[i] = arr[temp];
arr[temp] = temp;

如果有重复的数，由于arr[arr[i]]位置上的数已经被占了，所以这个时候我们就知道有重复的数，算法如下

public class Test01 {
    public static boolean duplicate(int[] arr) {

        if (arr.length <= 0 || arr == null) {
            return false;
        }

        for (int i = 0; i < arr.length; i++) {
            while(arr[i] != i) {
                if (arr[arr[i]] == arr[i]) {
                    return true;
                }

                swap(arr, i, arr[i]);
                printArr(arr);
            }
        }

        return false;
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    private static void printArr(int[] arr) {
        System.out.print("[");
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]);
            if(i != arr.length - 1) {
                System.out.print(", "); 
            }
        }
        System.out.println("]");
    }

    public static void main(String[] args) {
        int[] arr = {2, 3, 1, 0, 2, 3, 5};
        // int[] arr = {7, 5, 6, 3, 4, 1, 0, 2};
        boolean duplicated = duplicate(arr);
        System.out.println(duplicated);
    }
}

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

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

该算法有两种思路，第一种需要大小为 n+1 的辅助数组，我们遍历数组，将数组中的元素都复制到辅助数组中，原则如下，假设要复制的元素为m，那么将该数复制到辅助数组中下标为m的位置，这样很容易知道哪个元素重复了。

public class Test02 {
    public static int duplicate(int[] arr) {
        int N = arr.length;
        int[] helpArr = new int[N];

        for(int i = 0; i < N; i++) {
            if (arr[i] == helpArr[arr[i]]) {
                return arr[i];
            } else {
                helpArr[arr[i]] = arr[i];
            }
        }

        return -1;
    }

    public static void main(String[] args) {
        int[] arr = {2, 3, 5, 4, 3, 2, 6, 7};
        int num = duplicate(arr);
        System.out.println(num); // 3
    }
}

另一种思路是二分查找，首先我们将数字分成两半，比如 1~m 和 m+1~n，接着我们在数组中统计数字在 1~m 区间中的个数，如果数量大于 m ，那么就说明在 1~m 中有重复的数字，否则在 m+1~n 中有重复的数字，假设在 1~m 中有重复的数字，那么继续分成两半，如此往复，直到两边只有一个元素，代码如下

public class Test03 {
    public static int duplicate(int[] arr) {
        int start = 1;
        int end = arr.length - 1;
        
        while (end >= start) {
            int middle = start + (end - start) / 2;
            // 获得数字范围在[start, middle]范围内的数目
            int countNum = count(arr, start, middle);
            if (start == end) {
                if(countNum > 1) {
                    return start;
                } else {
                    // 如果范围只剩最后一个元素，但是数目不大于1，说明没有重复的
                    break;
                }
            }

            if (countNum > (middle - start + 1)) {
                // 在[start, middle]中继续找
                end = middle;
            } else {
                // 在[middle + 1, end]中继续找
                start = middle + 1;
            }
        }

        return -1;
    }

    // 统计数组中数字范围在[start, end]范围内的数目
    private static int count(int[] arr, int start, int end) {
        int count = 0;
        for(int i = 0; i < arr.length; i++) {
            if (start <= arr[i] && arr[i] <= end) {
                count++;
            }
        }

        return count;
    }

    public static void main(String[] args) {
        int[] arr = {2, 3, 5, 4, 3, 2, 6, 7};
        int num = duplicate(arr);
        System.out.println(num); // 3
    }
}