https://leetcode.cn/problems/find-the-duplicate-number/submissions/
方法1：pos记录无重复区间的下一个位置 （TLE）
def findDuplicate(self, nums: List[int]) -> int:
pos = 0
for i in range(len(nums)):
if nums[i] not in nums[:pos]:
nums[pos], nums[i] = nums[pos], nums[i]
pos += 1
else:
return nums[i]
方法2：二分查找
left, right = 1, len(nums) # 重复元素一定在1到n之间
1.假设mid是重复元素；统计数组中小于等于mid的元素个数cnt
2.如果cnt > mid，那么重复元素一定位于 [left...mid]
3.如果cnt < mid, 那么重复元素一定位于 [mid+1 ...right]
def findDuplicate(self, nums: List[int]) -> int:
# 1 2 2
# mid = 2
# cnt = 3 > mid ---> right = mid
left, right = 1, len(nums)
while left < right:
mid = (left + right) >> 1
cnt = 0
for num in nums:
if num <= mid:
cnt += 1
if cnt <= mid:
left = mid + 1
else:
right = mid
return left
方法3：快慢指针找环的入口
def findDuplicate(self, nums: List[int]) -> int:
# https://leetcode.cn/problems/find-the-duplicate-number/solution/287xun-zhao-zhong-fu-shu-by-kirsche/
slow, fast = nums[0], nums[nums[0]]
while slow != fast:
slow = nums[slow]
fast = nums[nums[fast]]
slow = 0
while slow != fast:
slow = nums[slow]
fast = nums[fast]
return slow