287. 寻找重复数
二分
二分并不是在nums数组上进行的，二分是在1 2 3 4 ... n上搜索的
cnt[i]表示比<=i的数有多少个
这里的cnt数组没必要都算出来。每次计算当前<=mid的cnt就行了。
- 问题、对比
这个返回l还要再思考思考，这个二分模板是l<=r为判断条件，yxc的是l<r为判断条件，这样返回l和r对应的值都一样了。 - 分析、解决
当最后要退出的时候:l=r=mid，这一次找的mid就是答案了，一定不会执行cnt<=mid的内容，而是r=mid-1的内容，这时候就是r+1=l=mid了，所以返回l是对的 - 反推、泛化
所以当l<=r为条件的时候，看里面的if l=mid+1和else r=mid-1哪个一定不会执行，才能判断最后l是对的位置还是r是对的位置
class Solution {
public:
int findDuplicate(vector<int>& nums) {
int l=1,r=nums.size()-1;
while(l<=r){
int mid=l+r>>1;
int cnt=0;
for(auto i:nums)cnt+=i<=mid;
if(cnt<=mid) l=mid+1;
else r=mid-1;
}
return l;
}
};
