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(i1,n1): if nums[i] nums[j]: return nums[i] return nums[0]解法2Floyd 环 快慢指针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