题目地址：https://www.acwing.com/problem/content/15/
AC代码——O(n)时间复杂度
class Solution {
public:
int duplicateInArray(vector<int>& nums) {
int f = 0, s = 0;
while (f == 0 || f != s) {
f = nums[f];
if(f==nums.size()) return -1;
f=nums[f];
if(f==nums.size()) return -1;
s = nums[s];
}
f = 0;
while (f != s) {
f = nums[f];
s = nums[s];
}
return s;
}
};
通常O(nlogn)二分解法
class Solution {
public:
int duplicateInArray(vector<int>& v) {
int l=1,r=v.size()-1,mid;
while(l<r){
int lcnt=0;
mid=l+((r-l)>>1);
for(int i=0;i<v.size();++i){
if(v[i]<=mid && v[i]>=l) lcnt++;
}
if(lcnt>mid-l+1) r=mid;
else l=mid+1;
}
return l;
}
};
