面試必考：龜兔賽跑算法

大家好，我是小梁！

今天和大家分享下一種實用且常見的算法：Floyd 判圈算法 (Floyd Cycle Detection Algorithm)，又稱龜兔賽跑算法 (Tortoise and Hare Algorithm)。

FLody 判圈算法在鏈表上的應用有如下三種：

  1. 檢測是否存在環

  2. 若環存在，可以計算出環的長度

  3. 若環存在，可以計算出環的起點

一. 算法原理證明

圖 1

如圖 1 已知兔子和烏龜

1. 環是否存在

結論： 若兔子在達到鏈表尾部前，烏龜與兔子相遇了，則說明鏈表有環。

反證法： 若環不存在，那麼烏龜永遠追不上兔子，那麼在兔子到達鏈表尾部前烏龜不會和兔子相遇。若相遇了，則鏈表有環。

2. 求環的長度

已知烏龜和兔子相遇時，它們必定都在環上。設它們第一次相遇在 B 點，相遇後兔子保持不動，烏龜保持每次移動一步的速度繼續前行，第二次相遇時，環長度 L = 第一次相遇後到第二次相遇時烏龜走過的路程。

3. 求環的起點

設烏龜走過的全部路程爲 i，那麼有

i = m + n + aL  （1）「a 是烏龜繞過的環的圈數」

因爲兔子的速度是烏龜的兩倍，所以有

2i = m + n + bL（2）「b 是兔子繞過的環的圈數」

(2) - (1) 可得：

i = (b - a)L     （3）

結合式子 (1)、(3) 可得 m + n + aL =  (b - a)L，所以有

m + n = (b-2a)L（4）{因爲 m+n>0 且 L>0, 所以 b-2a>=1}

所以可以得出結論：

m + n = 環長度 L 的正整數倍。（5）

當烏龜和兔子在 B 點第一次相遇後，讓烏龜回到起點 S，兔子仍在 B，烏龜以每次 1 步的速度向前走，兔子以相同的速度繞環逆時針前進。當走了 m 步時，兔子和烏龜都正好在 A 處，即環的起點。因爲兔子相對於 A 點走了 (n+m) 步，由結論 (5) 可知 A 必然是環的起點。

二. 舉一反三

知道 floyd 判圈法的原理後，我們來活學活用吧！請看題：

尋找重複數

首先明確前提，整數的數組 nums 中的數字範圍是 [1,n]。考慮一下兩種情況：

如果數組中沒有重複的數，以數組 [1,3,4,2] 爲例，我們將數組下標 n 和數 nums[n] 建立一個映射關係 f(n)f(n)，
其映射關係 n->f(n) 爲：
0->1
1->3
2->4
3->2
我們從下標爲 0 出發，根據 f(n)f(n) 計算出一個值，以這個值爲新的下標，再用這個函數計算，以此類推，直到下標超界。這樣可以產生一個類似鏈表一樣的序列。
0->1->3->2->4->null

如果數組中有重複的數，以數組 [1,3,4,2,2] 爲例, 我們將數組下標 n 和數 nums[n] 建立一個映射關係 f(n)f(n)，
其映射關係 n->f(n) 爲：
0->1
1->3
2->4
3->2
4->2
同樣的，我們從下標爲 0 出發，根據 f(n)f(n) 計算出一個值，以這個值爲新的下標，再用這個函數計算，以此類推產生一個類似鏈表一樣的序列。
0->1->3->2->4->2->4->2->……
這裏 2->4 是一個循環，那麼這個鏈表可以抽象爲下圖：

有環鏈表

從理論上講，數組中如果有重複的數，那麼就會產生多對一的映射，這樣，形成的鏈表就一定會有環路了，

綜上，可以將問題轉換成 Floyd 判圈算法

  1. 數組中有一個重複的整數 <==> 檢測鏈表中是否存在環

  2. 找到數組中的重複數 <==> 若環存在，可以計算出環的起點

來，上題解，下面的代碼是 c++ 版

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/gFGe648JjJZqOvdDdZn5Ng

猜你喜歡