【LeetCode教學】287. Find the Duplicate Number

C++, Cpp, Floyd Algorithm, LeetCode, Two Pointers

給定一個整數數組，找到其中唯一的重複數字。

題目連結：連結點此。

題目描述

給定一個整數數組 nums，其中包含 n + 1 個整數，每個整數都在 [1, n] 範圍內（包含 1, n）。

nums 中只有一個重複的數字，傳回這個重複的數字。

必須在不修改陣列 nums 的情況下，只使用常數額外空間來解決這個問題。

題目限制

  • 1 <= n <= 105
  • nums.length == n + 1
  • 1 <= nums[i] <= n
  • All the integers in nums appear only once except for precisely one integer which appears two or more times.

解題方法

題目其實不難，以下幾種方法都可以解：

  • 排序：排序傳入陣列nums後檢查相鄰元素是否相同，時間複雜度 O(n log n)，但會修改nums。
  • 哈希表：記錄每個數字的頻次，時間複雜度 O(n)，但空間複雜度為 O(n) 。
  • 雙重迴圈：檢查每個數字是否在後面重複，時複雜度間 O(n2)。

但是因為有不修改陣列、空間複雜度 O(1)、時間複雜度小於 O(n2)等限制，所以我們選用Floyd演算法（也稱龜兔演算法），它滿足題目所有要求。

Floyd演算法將陣列nums視為一個鏈結串列，nums[i] 表示指向下一個索引 nums[i] 的指針。

例如，nums = [1,3,4,2,2] 可看作索引 0 -> 1 -> 3 -> 2 -> 4 -> 2，形成環 2 -> 4 -> 2。

重複數字對應環的入口，因為多個索引指向它（例如，nums[2] = 2, nums[4] = 2 都指向索引 2）。

1. 變數宣告

首先我們需要兩個指針，一個跑得快、一個跑的慢。

int slow = nums[0];
int fast = nums[0];

2. 第一階段－找到兩個指針的相遇點

快指針每次走兩步，慢指針每次走一步。

do
{
    slow = nums[slow];  //慢指針走一步
    fast = nums[nums[fast]];  //快指針走兩步
}while (slow != fast);

為什麼慢指針走一步是 slow = nums[slow] 而不是 slow += 1

在 Floyd 演算法中，我們將 nums 視為一個「鏈結串列」（linked list），其中每個索引 i 是節點，下一個節點由 nums[i] 決定，而不是簡單的 i+1。

意思是陣列的值 nums[i] 定義了指針的移動方向，形成一個基於值的鏈結結構，而不是按索引順序移動。

使用 slow = nums[slow]，模擬了鏈結串列中的「下一個節點」邏輯。

Floyd 演算法的環檢測原理

Floyd 判圈算法假設存在一個環，且快慢指針通過不同速度（快指針走兩步，慢指針走一步）最終會在環內相遇。

為了讓指針進入環，必須按照 nums[i] 的值跳轉，而不是按索引順序移動。

例如，環 2 -> 4 -> 2 只有通過 nums[2] = 4, nums[4] = 2 的跳轉才能進入，而 slow + 1 無法模擬這種跳轉。

同時，題目保證 nums[i] 的範圍在 [1, n]，因此 slow = nums[slow] 不會越界（因為 nums[slow] 總是有效索引），這個限制確保指針移動始終在陣列內，且最終進入環。

3. 第二階段－找到環入口

從相遇點和起點各走一步，找到環入口後就是代表重複數字。

將慢指針移回到起點，快指針留在相遇點。

slow = nums[0];  //慢指針回到起點
while (slow != fast)
{
    slow = nums[slow];  //慢指針走一步
    fast = nums[fast];  //快指針走一步
}

為什麼第一階段使用do-while但是第二階段改用while

在第一階段開始時，快慢指針均初始化為 nums[0]。第一次迭代時，slow == fast，若使用 while (slow != fast)，迴圈條件一開始就不滿足（因為 slow == fast），導致迴圈立即退出，無法進行任何移動。

在第二階段開始時，慢指針重置為 nums[0]，快指針保持在第一階段的相遇點。如果此時 slow == fast，表示環入口已經找到，就無需進入迴圈。如果還是進入迴圈的話會導致錯誤的指針移動，反而得到錯誤的結果。

4. 回傳值

回傳找到的環入口（也就是重複數字）。

return slow;

這個題目雖然不難但概念可能比較難懂一點，可以用紙筆模擬快慢指針的移動就能理解Floyd演算法的運作方式。

完整程式碼

class Solution {
public:
    int findDuplicate(vector<int>& nums) {

        //Floyd演算法
        //1.初始化快慢指針
        int slow = nums[0];
        int fast = nums[0];

        //2.第一階段：快指針每次走兩步，慢指針每次走一步，找到相遇點。
        do
        {
            slow = nums[slow];  //慢指針走一步
            fast = nums[nums[fast]];  //快指針走兩步
        }while (slow != fast);

        //3.第二階段：從相遇點和起點各走一步，找到環入口（即重複數字）。
        slow = nums[0];  //慢指針回到起點
        while (slow != fast)
        {
            slow = nums[slow];  //慢指針走一步
            fast = nums[fast];  //快指針走一步
        }
        
        //4.環入口即為重複數字
        return slow;
    }
};

測試資料

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

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

Input: nums = [3,3,3,3,3]
Output: 3

時間與空間複雜度

時間複雜度：O(n)，快慢指針最多 O(n) 步找到相遇點和環入口。

空間複雜度：O(1)，僅用兩個指針。

其他相關題目

相關文章

返回頂端