龜兔賽跑算法（Floyd’s Cycle-Finding Algorithm）尋找重復數

問題描述

給定一個長度為 N+1 的數組 nums，其中每個元素的值都在 [1, N] 范圍內。根據鴿巢原理，至少有一個數字是重復的。請找出這個重復的數字。

要求：

• 時間復雜度 O(N)
• 空間復雜度 O(1)（不能使用哈希表等額外存儲）

---

算法思路（龜兔賽跑法）

我們可以將數組視為一個鏈表，其中 nums[i] 表示 i → nums[i] 的邊。由于存在重復數字，這個鏈表必然存在一個環，而環的入口就是重復的數字。

步驟：

1. 快慢指針找相遇點（判斷是否有環）：

   • 慢指針 slow 每次走 1 步：slow = nums[slow]
   • 快指針 fast 每次走 2 步：fast = nums[nums[fast]]
   • 直到 slow == fast，說明兩者在環內相遇。

2. 找環的入口（即重復的數字）：

   • 將 fast 重置到起點 0。
   • slow 和 fast 都每次走 1 步，直到再次相遇，相遇點就是重復的數字。

---

代碼實現

public int findDuplicate(int[] nums) {int slow = 0;int fast = 0;// 第一階段：快慢指針找相遇點do {slow = nums[slow];          // 慢指針走 1 步fast = nums[nums[fast]];     // 快指針走 2 步} while (slow != fast);// 第二階段：找環的入口（重復數字）fast = 0;while (slow != fast) {slow = nums[slow];fast = nums[fast];}return slow;  // 或 fast，此時它們相等
}

---

為什么這個算法有效？

1. 第一階段（找相遇點）：

   • 假設環的長度為 L，環外長度為 F。
   • 當 slow 進入環時，fast 已經在環內，且距離 slow 為 d（0 ≤ d < L）。
   • 由于 fast 每次比 slow 多走 1 步，它們會在 L - d 步后相遇。

2. 第二階段（找環入口）：

   • 設 slow 和 fast 在環內相遇時，slow 走了 F + a 步（a 是環內走的步數）。
   • fast 走了 F + a + kL 步（k 是整數，因為 fast 可能繞環多圈）。
   • 由于 fast 速度是 slow 的 2 倍：
     [
     2(F + a) = F + a + kL \implies F + a = kL \implies F = kL - a
     ]
   • 這意味著，從起點走 F 步，剛好到達環的入口（即重復數字）。

---

示例

輸入： nums = [1, 3, 4, 2, 2]
步驟：

1. 第一階段：
   • slow = 0 → 1 → 3 → 2 → 4 → 2 → 4 → ...
   • fast = 0 → 1 → 3 → 2 → 4 → 2 → 4 → ...
   • 它們在 2 或 4 相遇（具體取決于實現）。
2. 第二階段：
   • fast 重置到 0，然后 slow 和 fast 都每次走 1 步：
     • fast = 0 → 1 → 3 → 2
     • slow = 4 → 2
   • 它們在 2 相遇，因此 2 是重復數字。

---

復雜度分析

• 時間復雜度：O(N)（最多遍歷 2N 次）。
• 空間復雜度：O(1)（僅用兩個指針）。

---

總結

龜兔賽跑算法是一種高效的鏈表環檢測方法，適用于：

• 檢測鏈表是否有環。
• 找出數組中的重復數字（數組值在 [1, N] 范圍內）。
• 不修改原數組，且滿足 O(1) 額外空間。