Hot-287 寻找重复数

解法1：暴力搜索 - 超时

class Solution: def findDuplicate(self, nums: List[int]) -> int: # 暴力法：2个for循环: n = len(nums) - 1 for i in range(n): for j in range(i+1,n+1): if nums[i] == nums[j]: return nums[i] return nums[0]

解法2：Floyd 环 （快慢指针）

from typing import List class Solution: def findDuplicate(self, nums: List[int]) -> int: # 我懂了， # 第一步 # 你可以这么理解：对于数组nums=[num1,num2,num3 ... , numk] # 你按照从[nums[i]]索引的顺序来一个个添加进去 - 对应链表的构建过程 # 如果需要产生环，那么就一定要跳到原来的index上去，那之前也有这个index的跳跃 # 所以产生这两个相同跳跃的数值num_i 和 num_j 一定相同 # 所以一定只能是重复数字的位置可以产生环 # 并且index = 0 保证了 0 没有入度，也就是0一定不是环，可以作为入口 slow = nums[0] fast = nums[0] # 其实0也可以 while True: slow = nums[slow] fast = nums[nums[fast]] if slow == fast: break # 第二步 # 然后根据Floyd的环入口计算公式，让slow-fast相遇点 和 head 同时移动相遇在入口 head = nums[0] while slow != head: slow = nums[slow] head = nums[head] return slow