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)，不需要额外开辟新的空间。
