题目地址：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;
    }
};

总结

成环链表特点参考：https://www.cnblogs.com/xudong-bupt/p/3667729.html