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

    在一个长度为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]

    1. int temp = arr[i];
    2. arr[i] = arr[temp];
    3. arr[temp] = temp;

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

    1. public class Test01 {
    2.     public static boolean duplicate(int[] arr) {
    4.         if (arr.length <= 0 || arr == null) {
    5.             return false;
    6.         }
    8.         for (int i = 0; i < arr.length; i++) {
    9.             while(arr[i] != i) {
    10.                 if (arr[arr[i]] == arr[i]) {
    11.                     return true;
    12.                 }
    14.                 swap(arr, i, arr[i]);
    15.                 printArr(arr);
    16.             }
    17.         }
    19.         return false;
    20.     }
    22.     private static void swap(int[] arr, int i, int j) {
    23.         int temp = arr[i];
    24.         arr[i] = arr[j];
    25.         arr[j] = temp;
    26.     }
    28.     private static void printArr(int[] arr) {
    29.         System.out.print("[");
    30.         for (int i = 0; i < arr.length; i++) {
    31.             System.out.print(arr[i]);
    32.             if(i != arr.length - 1) {
    33.                 System.out.print(", "); 
    34.             }
    35.         }
    36.         System.out.println("]");
    37.     }
    39.     public static void main(String[] args) {
    40.         int[] arr = {2, 3, 1, 0, 2, 3, 5};
    41.         // int[] arr = {7, 5, 6, 3, 4, 1, 0, 2};
    42.         boolean duplicated = duplicate(arr);
    43.         System.out.println(duplicated);
    44.     }
    45. }

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

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

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

    1. public class Test02 {
    2.     public static int duplicate(int[] arr) {
    3.         int N = arr.length;
    4.         int[] helpArr = new int[N];
    6.         for(int i = 0; i < N; i++) {
    7.             if (arr[i] == helpArr[arr[i]]) {
    8.                 return arr[i];
    9.             } else {
    10.                 helpArr[arr[i]] = arr[i];
    11.             }
    12.         }
    14.         return -1;
    15.     }
    17.     public static void main(String[] args) {
    18.         int[] arr = {2, 3, 5, 4, 3, 2, 6, 7};
    19.         int num = duplicate(arr);
    20.         System.out.println(num); // 3
    21.     }
    22. }

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

    1. public class Test03 {
    2.     public static int duplicate(int[] arr) {
    3.         int start = 1;
    4.         int end = arr.length - 1;
    6.         while (end >= start) {
    7.             int middle = start + (end - start) / 2;
    8.             // 获得数字范围在[start, middle]范围内的数目
    9.             int countNum = count(arr, start, middle);
    10.             if (start == end) {
    11.                 if(countNum > 1) {
    12.                     return start;
    13.                 } else {
    14.                     // 如果范围只剩最后一个元素，但是数目不大于1，说明没有重复的
    15.                     break;
    16.                 }
    17.             }
    19.             if (countNum > (middle - start + 1)) {
    20.                 // 在[start, middle]中继续找
    21.                 end = middle;
    22.             } else {
    23.                 // 在[middle + 1, end]中继续找
    24.                 start = middle + 1;
    25.             }
    26.         }
    28.         return -1;
    29.     }
    31.     // 统计数组中数字范围在[start, end]范围内的数目
    32.     private static int count(int[] arr, int start, int end) {
    33.         int count = 0;
    34.         for(int i = 0; i < arr.length; i++) {
    35.             if (start <= arr[i] && arr[i] <= end) {
    36.                 count++;
    37.             }
    38.         }
    40.         return count;
    41.     }
    43.     public static void main(String[] args) {
    44.         int[] arr = {2, 3, 5, 4, 3, 2, 6, 7};
    45.         int num = duplicate(arr);
    46.         System.out.println(num); // 3
    47.     }
    48. }