面试题3：题目二 不修改数组找出重复的数字
在一个长度为n+1的数组里的所有数字都在1~n的范围内。所以数组中至少有一个数字是重复的。请找出数组中任意一个重复的数字，但不能修改输入的数组。例如，如果输入长度为8的数组{2，3，5，4，3，2，6，7}，那么对应的输出是重复的数字2或者3。
OC形式1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43...
NSArray *numbers = @[@(2),@(3),@(5),@(4),@(3),@(2),@(6),@(7)];
...
- (int)getDuplicationWithNumbers:(NSArray *)numbers length:(int)length {
if (numbers == nil || length <= 0) {
return -1;
}
int start = 1;
int end = length - 1;
while (end >= start) {
int middle = ((end - start) >> 1) + start;//取一个中间值
int count = [self countRangeWithNumbers:numbers length:length start:start end:end];
if (end == start) {
if (count > 1) {
return start;
}
else {
break;
}
}
if (count > (middle - start + 1)) {
//如果count大于middle到start这一段的数量，则说明重复数字必在这一段中，把middle设置为end，后续操作就在这一段中进行
end = middle;
}else {
//否则把start设置为middle的下一个，说明不在该组中必在另一组中
start = middle + 1;
}
}
return -1;
}
- (int)countRangeWithNumbers:(NSArray *)numbers length:(int)length start:(int)start end:(int)end {
if (numbers == nil) {
return 0;
}
int count = 0;
for (int i = 0; i < length; i++) {
int temp = [numbers[i] intValue];
if (temp >= start && temp <= end) {
++count;
}
}
return count;
}
时间复杂度
长度为n的数组，函数countRange将被调用O(logn)次，每次需要O(n)的时间，所以总的时间复杂度为O(nlogn)，空间复杂度为O(1)。该算法和需要辅助空间的算法相比相当于以时间换空间。
思路
利用二分查找的思路。
备注
该算法不能保证找出所有重复的数字。
拓展
>>1右移1此处起到除以2的效果