找出重複數字：Floyd Cycle Detection Algorithm 龜兔賽跑演算法

LeetCode 287 Find the Duplicate Number(M)

Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.

Example 1:

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

Example 2:

Input: [3,1,3,4,2]
Outp

直覺暴力法

看到題目的時候，想說這個 medium 題也太簡單就是找重複嘛😏
直接 sort 排序再前後比對

不過這樣寫雖然可以通過測試，但並不符合題目要求

Note:

1. You must not modify the array (assume the array is read only).
2. You must use only constant, O(1) extra space.
3. Your runtime complexity should be less than O(n2).
4. There is only one duplicate number in the array, but it could be repeated more than once.

Cycle Detection 方法

Pigeonhole principle 鴿籠原理

若有n個籠子和n+1隻鴿子，所有的鴿子都被關在鴿籠裡，那麼至少有一個籠子有至少2隻鴿子。

https://steemit.com/mathematics/@sinbad989/a-gentle-introduction-to-mathematics-the-pigeonhole-principle

題目給定一個 N 長度的陣列，此陣列中包含 N + 1 個元素，元素為 1 — N 的整數，則代表其中至少有一個數字是重複的。此重複的數字可以透過 Cycle Detection 來找到。

當有重複數字時，代表存在循環

Floyd Cycle Detection Algorithm 找出環的起點

假設同時一隻烏龜和一隻兔子從起點開始賽跑，烏龜一次跑一格，兔子一次跑兩格，一直跑下去如果他們能在某個地點會合，代表他們在環形跑道中。反之如果是直線跑道烏龜永遠追不上兔子。

1. 讓烏龜與兔子都在起點上

let hare = nums[0]      // 1
let tortoise = nums[0]  // 1

2. 開始賽跑，兔子一次走兩格、烏龜一次走一格直到他們相遇停止，此時兔子所走的距離是烏龜的兩倍 2d(tortoise)=d(hare)。

hare = nums[nums[hare]]    // 兔子走兩格 
tortoise = nums[tortoise]  // 烏龜走一格
while (hare !== tortoise) {     
    tortoise = nums[tortoise]       
    hare = nums[nums[hare]]    
}

假設兔子與烏龜在 Z 點第一次相遇 ，環周長為 F

烏龜走了 a + b + mF 的距離，不管烏龜前面走了幾圈只需要計算最後要相遇時小於環州長的距離 a + b
兔子也同樣有走了 mF 圈但比烏龜多走了 nF 圈 a + b + nF
兔子所走的距離為烏龜的兩倍所以

兔子走過的距離 2(a + b) = a + b + nF

a + b = nF
a = nF - b 
n 代表圈數，不論跑幾圈，每圈的起始點都會在同一個地方
所以我們可以先假設 n = 1 
則 a = F - b = c

3. 此時讓烏龜返回起始點，兩者以相同速度繼續前進，他們就會在 Y 點再次會合，也就是重複的數字。

tortoise = nums[0]   //烏龜回到原點
while(hare !== tortoise) {        
    tortoise = nums[tortoise]       
    hare = nums[hare]    
}