class Solution {
public:
int duplicateInArray(vector[HTML_REMOVED]& nums) {
//分治思想,因为数组的长度是n+1,而数的范围都在n~1范围内,所有必有一个数会重复,那么将该区间中的n+1个数按数值的取值范围取成两个区间
//有一个区间一定会比n/2多出来一个数,因为那个数是重复的,比如你想要找的区间是[1,2,3,3,4,5,6,7,8]那么你通过二分取得值域的中点,mid=(1+n)/2;mid=4
//那么将区间划分成了[1,2,3,4][5,6,7,8]这个区间然后在切割二原本的数组,将其变成了[1,2,3,3,4]和[5,6,7,8]这个区间,此时你会发现有一个区间的数的数量是大于mid-l的
//意味着值域[l,mid]这个值域范围内一定有一个重复的数字那么可以将搜索的范围缩小到[l,mid]这个值域中再次找寻一个重复的数,可以通过二分来实现逐步的迭代
int l=1;
int r=nums.size()-1;
while(l[HTML_REMOVED]>1;//划分值域
int s=0;
for(auto x:nums) s+=x>=l&&x<=mid;//统计数值位于[l,mid]范围内数的数量
if(s>mid-l+1) r=mid;//这个语句通过判断是否重复的数位于左侧区间,如果数量大于值域里面的数字的数量,那么就是说重复的数字在里面,并且mid这个点是有可能重复的数字
//是你想要求的答案所以将搜索的区间缩小到[l,mid]这个区间内
//这个说明右侧的数量大于了原本所界定的值域的数字的数量,那么就会往右边搜索,并且mid不在考虑的范围内所以mid+1缩小
else l=mid+1;
}
return l;
}
};