原题出处：https://leetcode.cn/leetbook/read/top-interview-questions-hard/xwz4lj/

解法一（python）:

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        slow = nums[0]
        fast = nums[0]
        while True:
            slow = nums[slow]
            fast = nums[nums[fast]]
            if slow == fast:
                break
        slow = nums[0]
        while slow != fast:
            slow = nums[slow]
            fast = nums[fast]
        
        return slow

            

思路：快慢指针，第一次遍历，慢指针走一步，快指针走两步，因为存在重复的值，所以总会有相等的时候，相等的时候结束遍历，

然后将慢指针设置为初始值，在和快指针以相同的步数前进，直到他们相等，如果他们相等了，这时返回快慢指针的其中一个就是那个重复的元素。

2023-10-06 start:

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        # 初始化二分查找的左右边界
        left, right = 1, len(nums) - 1
        
        while left < right:
            mid = (left + right) // 2  # 计算中间值
            count = 0
            
            # 统计数组中小于等于mid的元素个数
            for num in nums:
                if num <= mid:
                    count += 1
            
            # 根据抽屉原理，如果小于等于mid的元素个数大于mid，说明重复元素在左半部分
            if count > mid:
                right = mid
            else:
                left = mid + 1

        # 最终left和right会相等，它们都指向重复元素
        return left

思路：二分法

end