快慢指針題型

題目連結: 287. Find the Duplicate Number

題目描述:給你一個包含 n + 1 個整數的陣列 nums，其中每個整數都在 [1, n] 的範圍內（包含 1 和 n）。已知只有一個數字會重複（也可能重複多次），請你找出這個重複的數字。

Input: nums = [1,3,4,2,2]
Output: 2

Input: nums = [3,1,3,4,2]
Output: 3

Python

解題思路:

• 題目有給嚴格條件
  1. 不能修改原始陣列 nums。
  2. 只能使用常數級別的額外空間，即 O(1) 空間複雜度。
• 將陣列「看作」一個Linked List。
• 把每個索引 i 上的值 nums[i] 看作是從節點 i 指向節點 nums[i] 的next 指針。
• 接著演算法步驟與昨天的算法一樣。

class Solution:
    def findDuplicate(self, nums: List[int]) -> int:
        slow = nums[0]
        fast = nums[0]
        while True:
            slow = nums[slow]
            fast = nums[nums[fast]]
            if slow == fast:
                break
        pre = nums[0]
        while pre != slow:
            pre = nums[pre]
            slow = nums[slow]
        return pre

演算法分析:

• 初始化 slow = head, fast = head。
• if slow == fast:如果相遇就跳出迴圈。
• while pre != slow: 迴圈中，pre 和 slow 都以相同速度前進。

複雜度分析:

• 尋找相遇點與尋找環入口的迴圈裡指針移動的總步數都與陣列長度 n 呈線性關係。

• 因此，總時間複雜度為 O(n)。

• 空間複雜度： O(1)(只宣告了 fast、 slow、 pre)。

有問題可以底下留言!
下回見!!