題目描述
287. 尋找重復數 - 力扣（LeetCode）
定一個包含?n + 1?個整數的數組?nums?，其數字都在?[1, n]?范圍內（包括?1?和?n），可知至少存在一個重復的整數。
假設?nums?只有?一個重復的整數?，返回?這個重復的數?。
你設計的解決方案必須?不修改?數組?nums?且只用常量級?O(1)?的額外空間。
示例 1：
輸入：nums = [1,3,4,2,2] 輸出：2
示例 2：
輸入：nums = [3,1,3,4,2] 輸出：3
示例 3 :
輸入：nums = [3,3,3,3,3] 輸出：3
思路
數組當作一個鏈表來看，數組的下標就是指向元素的指針，把數組的元素也看作指針。如 0 是指針，指向 nums[0]，而 nums[0] 也是指針，指向 nums[nums[0]].
利用環形鏈表的思想，尋找環的入口
代碼
class Solution:
? ? def findDuplicate(self, nums: List[int]) -> int:
? ? ? ? # 環形鏈表的思想，尋找環的入口
? ? ? ? slow = fast = 0
? ? ? ? while True:
? ? ? ? ? ? fast = nums[fast]
? ? ? ? ? ? fast = nums[fast]
? ? ? ? ? ? slow = nums[slow]
? ? ? ? ? ? if fast == slow:
? ? ? ? ? ? ? ? break
? ? ? ??
? ? ? ? head = 0
? ? ? ? while head != slow:
? ? ? ? ? ? head = nums[head]
? ? ? ? ? ? slow = nums[slow]
? ? ? ? return slow
)
