class Solution {
public:
int duplicateInArray(vector<int>& nums) {
//按值二分
int n = nums.size() - 1,cnt;
int l = 1,r = n;
while(l < r){
cnt = 0;
int mid = l + r >> 1;
for(auto x:nums) if(x >= l && x <= mid) cnt++;
if(cnt > mid - l + 1) r = mid;
else l = mid + 1;
}
return l;
/*
int n = nums.size() - 1;
unordered_map<int,int> cnt;
for(auto x:nums){
if(x >= 1 && x <= n)
cnt[x]++;
if(cnt[x] > 1) return x;
}
return -1;*/
}
};