思路
抽屉原理:n个位置,n+1个数
二分法
时间复杂度
O(nlgn)
C++ 代码
class Solution {
public:
int duplicateInArray(vector<int>& nums) {
int l=1,r=nums.size()-1;
while(l<r){
int mid = l+r>>1;
int x=0;
for(auto s:nums) x+= s>=l&s<=mid;
if(x>mid-l+1) r=mid;
else l=mid+1;
}
return r;
}
};