# A.题目一 在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。 例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是重复的数字2或者3。 ## 1.1 问题解析 - 长度为n的数组，数字为0~n-1的范围 - 可能有一个或多个重复数字也可能没有 - 输出其中一个重复数字即可 ## 1.2 思路连接 1. 首先想到将无序数组排序，然后从头到尾扫描排序数组。排序的时间复杂度为$O(nlogn)$ 2. 如果要将时间复杂度降到$O(n)$，可以考虑定义一个HashMap，每次判断是否存在，但是因为使用了哈希表，空间复杂度为$O(n)$ 3. 那是否有一个时间复杂度$O(n)$，空间复杂度又为$O(1)$的算法呢？题目中说到数组元素都在0~n-1的范围内，如果数组中没有重复数字，那么排序后的数字就在与其相同的索引值的位置，如数字2应该在第2个位置上。遍历的过程中寻找位置和元素不相同的值，并进行交换排序。如果交换位置的时候发现两个值相等，即为重复数字 4. 依照惯例，最后要注意检查边界值以及特殊情况 ## 1.3 代码解答 ```java public static void main(String[] args) {     int[] numbers = {2, 3, 4, 1, 0, 2, 5};     System.out.println(duplicate(numbers)); } public static int duplicate(int[] numbers) {     if (numbers == null || numbers.length == 0) {         throw new RuntimeException("输入为空");     }     for (int i : numbers) {         if (i < 0 || i >= numbers.length) {             throw new RuntimeException("输入参数不合法");         }     }     for (int i = 0; i < numbers.length; ) {         if (numbers[i] != i) {             int temp = numbers[i];             if (numbers[i] == numbers[temp]) {                 i++;                 return numbers[temp];             } else {                 numbers[i] = numbers[temp];                 numbers[temp] = temp;             }         } else {             i++;         }     }     return -1; } ``` # B.题目二 在一个长度为n+1的数组里的所有数字都在1~n的范围内，所以数组中至少有一个数字是重复的。请找出数组中任意一个重复的数字，但是不能修改输入的数组。例如，如果输入长度为8的数组{2,3,5,4,3,2,6,7}，那么对应的输出是重复的数字2或者3。 ## 2.1 问题解析 - 长度为n+1的数组，数字为1~n的范围 - 至少有一个数字重复 - 不能修改输入的数组 - 输出其中一个重复数字即可 ## 2.2 思路连接 1. 这次的题目对比题目一不同的地方是不能修改输入数组了，所以题目一的解法不能使用了 2. 我们依旧可以考虑使用辅助数组或者HashMap的方式，时间复杂度$O(n)$，空间复杂度又为$O(n)$ 3. 上面说的辅助数组的时间复杂度虽然不错，不过毕竟空间复杂度占用挺高，我们考虑使用二分法查找的方式来解决这道题。我们把从`1~n`的数字从中间的数字m分为两部分，前面一半为`1~m`，后面一半为`m+1~n`。如果`1~m`的数字的数目大于m，那么这一半的区间一定包含重复的数字；否则，另一半`m+1~n`的区间里一定包含重复的数字。接下来，我们可以继续把包含重复的数字的区间一分为二，直到找到一个重复的数字。这个算法的时间复杂度$O(nlogn)$，仅供算法学习使用。 4. 依照惯例，最后要注意检查边界值以及特殊情况。 ## 2.3 代码解答 ```java public static void main(String[] args) {     int[] numbers = {2, 3, 5, 4, 3, 2, 6, 7};     System.out.println(duplicate(numbers)); } public static int duplicate(int[] numbers) {     if (numbers == null || numbers.length == 0) {         throw new RuntimeException("输入为空");     }     for (int number : numbers) {         if (number < 1 || number >= numbers.length) {             throw new RuntimeException("输入参数不合法");         }     }     int start = 1;     int end = numbers.length - 1;     while (end > start) {         int middle = ((end - start) >> 1) + start;         int count = countRange(numbers, start, middle);         if (count > (middle - start + 1)) {             end = middle;         } else {             start = middle + 1;         }     }     return start; } public static int countRange(int[] numbers, int start, int end) {     int count = 0;     for (int number : numbers) {         if (number >= start && number <= end) {             ++count;         }     }     return count; } ```