287. Find the Duplicate Number

題目連結: 287. Find the Duplicate Number

題目描述

給定一個包含 n + 1 個整數的陣列 nums，這些整數都在 1 到 n 之間（包括 1 和 n）。陣列中只有一個數字重複出現，請找出這個重複的數字。

要求：

• 不能修改陣列（例如不能對陣列進行排序）。
• 只能使用額外的 O(1) 空間。
• 時間複雜度小於 O(n²)。
• 陣列中只有一個數字重複出現兩次或多次，其餘數字只出現一次。

限制條件

• 1 <= n <= 10^5
• nums.length == n + 1
• 1 <= nums[i] <= n
• nums 中除了重複的數字外，其餘數字只出現一次。

解題思路

由於不能修改陣列且只能使用 O(1) 額外空間，我們需要找到一種不需要改變原始陣列的方法。這裡可以採用快慢指標法（Floyd's Tortoise and Hare Algorithm），該算法常用於檢測鏈結串列中的環。

關鍵觀察：

• 將陣列視為鏈結串列：我們可以將每個陣列元素視為鏈結串列中的節點，其中數值代表下一個節點的索引。例如，nums[i] 代表下一個節點的索引。
• 存在循環：由於存在重複的數字，會導致多個節點指向同一個節點，從而形成環。

步驟：

1. 初始化快慢指標：
   • 設置兩個指標 slow 和 fast，初始值為 nums[0]。
   • slow 每次移動一步，slow = nums[slow]。
   • fast 每次移動兩步，fast = nums[nums[fast]]。
2. 第一次相遇：
   • 在循環中，當 slow == fast，表示兩個指標在環中相遇。
3. 尋找環的入口（重複的數字）：
   • 將 fast 重置為 nums[0]。
   • 之後，slow 和 fast 每次都移動一步，slow = nums[slow]，fast = nums[fast]。
   • 當 slow == fast 時，相遇點即為環的入口，也就是重複的數字。

程式碼

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        if (nums.size() <= 1) {
            return -1;
        }

        int fast = 0;
        int slow = 0;
        do {
            slow = nums[slow];
            fast = nums[nums[fast]];
        } while (slow != fast);

        fast = 0;
        while (fast != slow) {
            fast = nums[fast];
            slow = nums[slow];
        }
        return slow;
    }
};

時間與空間複雜度分析

• 時間複雜度：O(n)
  • 分析：
    • 第一次迴圈（找相遇點）：
      • 快指標每次前進兩步，慢指標每次前進一步。
      • 由於存在環，快指標會在環內繞圈，最終與慢指標相遇。
      • 該過程最多需要走 n 步。
    • 第二次迴圈（找環的入口）：
      • 快慢指標從不同的起點，每次前進一步。
      • 由於兩指標之前的距離以及環的長度，最終會在環的入口相遇。
      • 該過程最多需要走 n 步。
    • 總計：兩次迴圈的步數總和為 O(n)。
• 空間複雜度：O(1)
  • 分析：
    • 只使用了固定數量的變數：slow、fast，不依賴於輸入大小。

詳細說明

• 為什麼可以將陣列視為鏈結串列？
  • 因為陣列中的每個值都在 1 到 n 之間，可以將 nums[i] 視為下一個節點的索引，這樣就構成了一個鏈結串列。
• 為什麼會有環？
  • 由於有一個數字重複，導致多個索引指向同一個節點，形成了環。
• 為什麼快慢指標相遇後，將快指標重置能找到環的入口？
  • 根據 Floyd's Tortoise and Hare Algorithm 的特性，相遇點到環的入口的距離等於起點到環的入口的距離。因此，同時移動兩個指標，當它們再次相遇時，所指向的節點即為環的入口。