当前位置：网站首页>leetcode：287. 寻找重复数【快慢指针板子】

leetcode：287. 寻找重复数【快慢指针板子】

2022-07-17 06:56:00 【白速龙王的回眸】

在这里插入图片描述

分析

n->nums[n]这样子
由于有至少一对ij使得nums[i] == nums[j]
所以肯定会有环的
环的入口就是重复的数字 nums[i]
快慢指针解决
第一次相遇后，重新从0走和当前位置走
再次相遇就是入口

ac code

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        # v in nums: v < len(nums)
        # n -> f(n), 成环

        # 找相遇点
        slow, fast = nums[0], nums[nums[0]]
        while slow != fast:
            slow = nums[slow]
            fast = nums[nums[fast]]
        
        # 找入口
        pre1 = slow
        pre2 = 0
        while pre1 != pre2:
            pre1 = nums[pre1]
            pre2 = nums[pre2]
        
        return pre1