LeetCode热题100-寻找重复数

张开发
• 2026/4/21 17:23:23 • 15 分钟阅读

最新文章

推荐文章

相关文章

分享文章

LeetCode热题100-寻找重复数
给定一个包含n 1个整数的数组nums其数字都在[1, n]范围内包括1和n可知至少存在一个重复的整数。假设nums只有一个重复的整数返回这个重复的数。你设计的解决方案必须不修改数组nums且只用常量级O(1)的额外空间。题目要求不能修改nums且空间复杂度为O1下面的方法虽可以通过但是不符合空间复杂度要求。class Solution: def findDuplicate(self, nums: List[int]) - int: seen set() for num in nums: if num in seen: return num seen.add(num)第二种方法快慢指针将数组看作链表循环遍历链表若有重复数一定存在环。只需要2步第一步让快慢指针相遇慢指针龟每次走 1 步slow nums[slow]快指针兔每次走 2 步fast nums[nums[fast]]因为有环它们一定会在环里某个点相遇。相遇不代表找到重复数只是证明这里有环。第二步把慢指针放回起点然后慢指针从头开始走每次 1 步快指针从相遇点开始走每次 1 步它们最终会在环的入口点相遇。环的入口 重复数字class Solution: def findDuplicate(self, nums: List[int]) - int: slow, fast 0, 0 while True: slow nums[slow] fast nums[nums[fast]] if slow fast: break slow 0 while slow ! fast: slow nums[slow] fast nums[fast] return slow

更多文章