力扣 287. 寻找重复数

二分查找

def findDuplicate(nums):
    # 二分查找
    left, right = 1, len(nums) - 1
    while left < right:
        mid = (left + right) >> 1
        count = 0
        for n in nums:
            if n <= mid:
                count += 1
        if count <= mid:
            left = mid + 1
        else:
            right = mid

    return left

双指针

def findDuplicate(nums):
    # 双指针
    low, fast = nums[0], nums[nums[0]]
    while low != fast:
        low = nums[low]
        fast = nums[nums[fast]]
    fast = 0
    while low != fast:
        low = nums[low]
        fast = nums[fast]
    return fast