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 的区间里一定包含重复的数字。
以长度为 8 的数组 {2,3,5,4,3,2,6,7} 为例分析查找的过程。长度为 8 所以中间的数字为 4,把这个数组分为两部分,一段是 1~4,另一部分是 5~7。接下来统计 1~4 这 4 个数字在数组中出现的次数,它们一共出现了 5 次,因此这 4 个数字中一定存在重复的数字。
接下来把 1~4 的范围一分为二,一段是 1、2 两个数字,另一段是 3、4 两个数字。数字 1、2 出现了两次,因此统计 3、4 出现的次数,它们一共出现了三次,因此存在重复的数字。再分别统计 3 和 4 出现的次数,最终输出的结果是 3。
3. 代码
public int solution2(int[] numbers){
if(numbers==null || numbers.length<=0)
return -1;
int start = 1;
int end = numbers.length;
while(start<=end){
int mid = (start+end)/2;
int count = countRange(numbers,start,mid);
if(start==end){
if(count>1)
return start;
else
break;
}
if(count>(mid-start+1))
end = mid;
else
start = mid+1;
}
return -1;
}
private int countRange(int[] numbers,int start,int end){
int count = 0;
for(int i=0;i<numbers.length;i++){
if(numbers[i]>=start && numbers[i]<=end)
count++;
}
return count;
}