[LeetCode] 287. Find the Duplicate Number

題目連結:287. Find the Duplicate Number

在開始說明解法之前想先分享一部有趣的影片，影片中剛好有出現這一題。

解題思路

#

這一題乍看之下好像不太難，只需要先把陣列做排序，然後找出相鄰元素是一樣的；或是維護一個 hashmap 來檢查元素之前是否有出現過。

但是題目有一些額外要求：

1. 不能修改原先的陣列。
2. 空間複雜度必須是 O(1)。

第一點要求限制了我們不能對原先的陣列做排序，而第二點讓我們沒辦法使用 hashmap。因此必須使用其他方法來解出這題。

Floyd’s Tortoise and Hare Algorithm 龜兔賽跑演算法

#

這個演算法原先是用來檢測 linked list 中是否存在迴圈 (cycle)。

確認是否有迴圈

#

假設有烏龜與兔子從原點出發，烏龜一次走一步，兔子一次走兩步。因為兔子走的比烏龜快，所以如果 linked list 中存在迴圈，兔子最後將會從後方倒追到烏龜。

尋找迴圈的起點

#

如果想要找到迴圈開始的起點，在烏龜與兔子第一次相遇時，將烏龜退回原點，兔子在原地不動，烏龜與兔子每次移動都只走一步。當烏龜與兔子再次相遇之處便是迴圈的起點。

這題雖然是一個陣列，但是可以把陣列的索引 (index) 當成是 linked list 節點的位址，陣列的值 (value) 則可以當成 linked list 中下一個節點的位址。陣列就變成像是 linked list 的結構。

這時可以觀察到，如果陣列中擁有重複的元素，代表會有兩個節點同時指到同一個節點，這時就會形成迴圈。例如範例測資 1 (Example 1)：0→1, 1→3, 3→2, 2→4, 4→2。而這個重複的元素，便會是迴圈的起點。

因此這題的解法為：

1. 維護 slow 和 fast 兩個 pointer，slow 每次移動一步，fast 每次移動兩步。
2. 如果 slow 與 fast 相遇了，則把 slow 移動到原點，fast 固定不動。
3. 接下來 slow 與 fast 每次都只移動一步，當 slow 與 fast 再次相遇時，slow 或是 fast 的值便是重複的元素。

程式碼

#

C++

#

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        int slow = nums[0], fast = nums[0];

        while (true) {
            slow = nums[slow];
            fast = nums[nums[fast]];
            if (slow == fast)
                break;
        }

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

        return slow;
    }
};

Python

#

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
        
        slow = nums[0]
        while slow != fast:
            slow = nums[slow]
            fast = nums[fast]
        
        return slow