繼第 10 天的「73. Set Matrix Zeroes」，今天來解 287 這題！還沒看過第 10 天或再之前天數的朋友，歡迎也去看看~

話不多說，我們開始吧！

基本資訊

• 難度： Medium
• 網址： https://leetcode.com/problems/find-the-duplicate-number/

演算法與資料結構

• 龜兔賽跑

題意

給予一個整數陣列，包含 n + 1 個整數，而元素的值在 `[1, n]`` 中

在所有元素只有一個數值會重複，請回傳重複的數值。

• 請勿變更陣列內容
• 必須只使用常數個多餘空間

Follow up

• 能不能用線性走訪解決？

解說

視元素的值為索引

• 數值在 1 到 n 之間
• 陣列長度為 n + 1

以 n = 4 為例，可用數值為

1, 2, 3, 4

可能的組合有像是

[1, 3, 4, 4, 2]

如果以元素的值作為索引，走訪順序就會像是這樣

   [0] 1 
-> [1] 3
-> [3] 4
-> [4] 2
-> [2] 4
-> [4] 2
...

就會發現到後面會進入一個循環。當出現循環，就可以項 linked list 一樣使用龜兔賽跑的方式找出循環的起點，來試著圖形化看看

+-----+-----+-----+-----+-----+
| [0] | [1] | [2] | [3] | [4] |
+-----+-----+-----+-----+-----+
|  1  |  3  |  4  |  4  |  2  |
+-----+-----+-----+-----+-----+

走訪方式：

+---+    +---+    +---+    +---+
| 1 | -> | 3 | -> | 4 | -> | 2 |
+---+    +---+    +---+    +---+
                    ^        |
                    |        |
                    +--------+

龜兔賽跑

尋找相遇點

在尋找相遇點的時候，龜兔賽跑會用到雙指標，一為 slow 一為 fast

• slow: 走一步
  • nums[slow]
• fast: 走兩步
  • nums[nums[fast]]

步驟：

+-----+-----+-----+-----+-----+
| [0] | [1] | [2] | [3] | [4] |
+-----+-----+-----+-----+-----+
|  1  |  3  |  4  |  4  |  2  |
+-----+-----+-----+-----+-----+

再次以範例來執行看看

(slow, fast)
   ([0], [0]) // 值 1, 1 (初始值)
-> ([1], [3]) // 值 3, 2
-> ([3], [2]) // 值 4, 4

找到相同的值後則停止，

但是相遇有可能是循環中的任一元素，因此我們還要設法找到循環的起點。

尋找循環的起點

這時候把 slow 維持在原本的位置，只把 fast 歸零，改為和 slow 指標一步一步前進

• slow: 走一步
  • nums[slow]
• fast: 走兩步
  • nums[fast]

步驟：

(slow, fast)
   ([3], [0]) // 值 4, 1
-> ([4], [1]) // 值 2, 3
-> ([2], [3]) // 值 4, 4 <-- 相遇，回傳 4
-> ([4], [4])

程式碼

class Solution {
    func findDuplicate(_ nums: [Int]) -> Int {
        let intersectionIndex = findIntersectionIndex(nums)
        return findStartIndex(nums, intersectionIndex)
    }
    
    /// 找出交叉的位置
    func findIntersectionIndex(_ nums: [Int]) -> Int {
        var slow = nums[0]
        var fast = nums[0]
        
        repeat {
            slow = nums[slow]
            fast = nums[nums[fast]]
        } while slow != fast
        
        return slow
    }
    
    /// 找出環狀的起始點
    func findStartIndex(_ nums: [Int], _ intersection: Int) -> Int {
        var slow = nums[0]
        var fast = intersection
        
        while slow != fast {
            slow = nums[slow]
            fast = nums[fast]
        }
        
        return slow
    }
}

執行結果

• Runtime: 644ms (Beats 97.89%)
• Memory: 18.50MB (Beats 40.99%)

複雜度分析

陣列有 n + 1 個元素，簡化為 n

結語

如果有什麼問題和回饋歡迎留言一起討論，今天就到這裡，明天見！