Sofie 舒霏的部落格

今天要來解的題目是 Leetcode－287. Find the Duplicate Number，難度為中等，

而我所使用的語言是 python3

壹、理解題目

Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive.

There is only one repeated number in nums, return this repeated number.

Example 1:

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

Example 2:

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

Example 3:

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

Example 4:

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

Constraints:

• 2 <= n <= 3 * 104
• 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.

用中文說，就是給定一個大小 n 的 array，裡面會出現的數字只可能是 1～n-1，

那就代表一定有重複的數字，

而在題目的設定之中，只可能有一個數字重複兩次（或更多），

我們要找到的，就是那個重複的數字。

貳、開始解題

以下是我第一版的想法，

既然只可能出現的數字只有 1～n-1，

那就創一個跟 nums 相同大小的 array（我稱為 cnt），全部初始化為 0，

接著掃過 nums，出現數字 i，那就在 cnt 的第 i 位 +1，

用 Example 1 舉例說明：

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

創建的 cnt array 原本為 [0,0,0,0,0]，

掃過 nums array 後，cnt 應該會變成 [0,1,2,1,1]

（也就是，數字 0 有 0 個、數字 1 有 1 個、數字 2 有 2 個、數字 3 有 1 個、數字 4 有 1 個），

那我們就找出在 cnt array 中大於 1 的就好，在這個例子中是數字 2。 

直接給 code！

這樣的複雜度呢？

空間複雜度應該滿明顯，因為額外開了和 nums 一樣大小的 cnt array，

所以空間複雜度就是 O(n)；

至於時間複雜度，在 call len(nums) 那行時，就 O(n)

接著的 for loop 最糟的情況也是 O(n)

所以 O(n) + O(n) = O(n)！

結果：Accepted！

而且 runtime 因為是 O(n)，看起來頗快耶！不過 memory usage 就普普

參、有更好的做法嗎？

有的！有個解法可以維持時間複雜度 O(n)，但空間複雜度卻降到 O(1)

但這沒碰過還真想不到，Floyd's Tortoise and Hare (Cycle Detection)

沒錯，這個題目可以轉換成 linked list cycle。

拆成兩步驟：

1. 轉換成 linked list（且可保證一定有 cycle）

以下方 example 舉例：

假設 nums 為一個 [2, 6, 4, 1, 3, 1, 5] 的序列，

從 nums[0] (=2) 出發，

下一個點呢？找到 nums[nums[0]] = nums[2] = 4 的位子

再下一個點呢？nums[nums[nums[0]]] = nums[nums[2]] = nums[4] = 3 的位子 

再下一個點呢？nums[nums[nums[nums[0]]]] = nums[nums[nums[2]]] = nums[nums[4]] = nums[3] = 1 的位子

再下一個點呢？nums[nums[nums[nums[nums[0]]]]] = nums[nums[nums[nums[2]]]] = nums[nums[nums[4]]] = nums[nums[3]] = nums[1] = 6 的位子

舉這麼多例，應該有感覺了吧？

還是沒有感覺？直接看圖比較直觀。

觀察到了嗎？重複出現的數字 1 就是 cycle 的頭

所謂「頭」是指，開始無限輪迴 1、6、5 這個 cycle 的起始點。

阿為什麼一定會有 cycle 咧？

有 n 個數字，但數字只可能是 1 ~ (n-1)，表示一定有重複，那就表示一定有 cycle 啊～

（也有可能某些數字永遠不會被 traverse 到，i.e. 一開始就在 loop裡面，可以試試上面的 example 2）

讀到這步，應該知道如何從給定的 nums 轉換成 linked list 了！

要先確認讀懂了，再繼續往下喔～

2. 找到該 cycle 的頭

好，我們目前知道要找到「duplicate number」就是「cycle head」，

那要怎麼找到「cycle head」呢？

用 Floyd Cycle Detection Algorithm！

維基：又稱龜兔賽跑算法(Tortoise and Hare Algorithm)，是一個可以在有限步數判斷是否存在 cycle，且求出該 cycle 的起點與長度的算法

在這裡，我們只要找到起點就好。

此演算法又分做兩個部分：

a. hare 走兩步、tortoise 走一步，直到兩者相遇

一定會相遇？一定會，因為有 cycle。

hare 想當然會先進 cycle 嘛，人家跑比較快，

然後當 tortoise 也進到 cycle 時，因為 hare 跑得快，有一天會倒追到 tortoise，

倒追到的那個時候，就是相遇的時候，此時要進下一階段。

b. tortoise 回到原點，而 hare 每次只走一步 (just like tortoise)，直到兩者相遇

直接說結論：這次的相遇一定會在 cycle head。

所以這時候就可以回傳兩者相遇時的那個數值了！Solved！

為何一定會在 cycle head 相遇？來證明吧！

所有的 case 都可以簡化成以下的圖

L 是起始點和 cycle head 的距離、x 是 cycle head 到第一次見面的距離、C 是整個 cycle 的長度

其中，L, x 都可以是 0

（L = 0 代表一開始就在 cycle；x = 0 代表剛剛好第一次遇到就是在 cycle head）

第一次相遇可以寫一個等式：2(L+x) = L+nC+x

(L+x) 代表 tortoise 走的步數，(L+nC+x) 是 hare 走的步數，

為何 hare 多 + 了 nC，因為我們不能確定 hare 在等到 tortoise 來之前，繞了幾次 cycle 了。

還記得 a. part 嗎？（hare 走兩步、tortoise 走一步，直到兩者相遇）

所以 tortoise 走的步數要乘以 2。

又，該等式可以簡化成 L+x = nC

接著，要證明一定會在 cycle head 相遇：

讓 tortoise 回到起點 (0)，走 L 步到 cycle head (L) 的同時，

hare 從第一次相遇的地方 (L+x)，走了一樣的步數 L 會到哪？

(L+x)+L 代入上面得到的 = nC+L 阿不就是 L 的位子, i.e. cycle head 嗎！

程式碼來！

結果：Accepted！