class Solution {
    public int findDuplicate(int[] nums) {
        // 1.二分查找 计算数组中小于等于该元素数量的个数，如果数量 > 该元素的值，说明，重复元素在l,元素区间内
        // 2.Floyd判圈算法
        // 快慢指针找相遇点 慢指针一次走一步，快指针一次走两步
        // 然后将其中一个指针移动到出发点
        // 两个指针的相遇点即为所求
        // 可以以i->nums[i]构建链表，有重复数字，说明有环
        int low = 0, high = nums.length -1;
        while (low < high) {
            int mid = low + (high - low) / 2;
            int count = 0;
            for (int i = 0; i < nums.length ; i++) {
                if (nums[i] <= mid) {
                    count++;
                }
            }
            if (count <= mid) {
                low = mid + 1;
            } else {
                high = mid ;
            }
        }
        return low;
    //    int slow = nums[0];
    //    int fast = nums[nums[0]];
    //    while (slow != fast) {
    //         slow = nums[slow];
    //         fast = nums[nums[fast]];
    //    }
    //    fast = 0;
    //    while (slow != fast) {
    //         slow = nums[slow];
    //         fast = nums[fast];
    //    }
    //    return fast;
    }
}