本题与3-1基本相同，不同之处在于数组不能修改，考虑辅助数组可采用3-1解法进行求解，以空间代价进行求解。
1.题目描述
在一个长度为n+1的数组里的所有数字都在1~n的范围内，所以数组中至少存在一个数字是重复的。请找出数组中任意一个重复的数字，但不能修改输入的数组。例如输入长度为8的数组{2，3，5，4，3，2，6，7}，那么对应的输出是重复的数字2或者3。
2.不同解法
考虑类似二分查找进行搜索，对1~n范围内的数值进行二分，若数组中在所限定范围内的元素个数大于范围值，则在此范围内必然有重复数字。
如{1,2,4,3,3}，考虑1~5范围取一半1~3，统计在此范围内的元素个数为4，表明1~3内有重复元素，再进行二分。
1 public static int getRepeatNumber(int[] array) {
2 // Judge the boundary of this problem
3 int len = array.length;
4 if (len == 0) {return -1;}
5 int lo = 1;
6 int hi = len - 1;
7 while(lo <= hi) {
8 int mid = (hi + lo) / 2;
9 int count = 0;
10 for (int n:
11 array) {
12 if (n >= lo && n <= mid) {
13 count++;
14 }
15 }
16 if (hi == lo) {
17 if (count > 1) {
18 return hi;
19 } else {
20 break;
21 }
22 }
23 if (count > mid - lo + 1) {
24 hi = mid;
25 } else {
26 lo = mid + 1;
27 }
28 }
29 return -1;
30 }复杂度分析：时间复杂度O(nlogn)，空间复杂度O(1)。