我有一個指針數組（這是算法，所以不要進入語言細節）。大多數情況下，這個數組指向數組之外的位置，但是它會降低到數組中每個指針指向數組中另一個指針的地步。最終，這些指針形成一個無限循環。如何在指針數組中找到無限循環？
所以在整個陣列由指針到陣列中的其他位置，你從頭開始的假設，你怎麼能找到環在時間和空間效率最高的長度？我相信最好的時間效率是O（n），因爲你必須循環陣列，最好的空間效率是O（1），但我不知道如何實現。
Index: 0 1 2 3 4 5 6
Value: *3 *2 *5 *4 *1 *1 *D
D是循環開始前指向的數據。在這個例子中，週期是1,2,5，並且它無限重複，但是索引0,3和4不是週期的一部分。
這是週期檢測問題的一個實例。 1960年Robert W. Floyd發現了一種優雅的O(n)時間O(1)空間解決方案;它通常被稱爲"Tortoise and Hare"算法，因爲它包括用兩個指針遍歷序列，其中一個移動的速度是另一個的兩倍。
這個想法很簡單：循環必須有一個長度爲k的循環，對於某些k。在每次迭代中，兔子移動兩步，烏龜移動一步，因此它們之間的距離比前一次迭代中的距離大1。因此，每個k迭代，因此它們是彼此分開的k步的倍數，並且一旦它們都處於週期中（這將在烏龜到達時發生），如果它們是k10步的間隔的倍數，則它們都指向相同的元素。
如果你只需要知道週期的長度，你就等待兔子和烏龜到達同一個地點;然後你沿着這個循環前進，計數步驟，直到你再次回到同一個點。在最壞的情況下，步驟的總數將是尾部的長度加週期長度的兩倍，該長度必須小於元素數量的兩倍。
注：第二段編輯爲可能使理念「更明顯」，不管這可能意味着。正式的證明很簡單，實施也很簡單，所以我也沒有提供。
我其實並不認爲Tortoise和Hare的證明與維基頁面看起來一樣微不足道（在數學/ CS範圍內是微不足道的，是的，在介紹類的範圍內，沒有）。我也不明白爲什麼你的段落證明他們必須在'k'步驟之後指向相同的元素（或者至少你需要寫出表達式來顯示它）。我用'dist = n +（k - （n％k））= yk'來證明自己的某些整數y。算法的下一步需要類似的簡短證明。 – rliu
我可以在沒有形式證明的情況下直觀地證明它（展開兔子走過的路徑，然後一遍又一遍地滾動，直到烏龜和兔子相遇）;但是你給出的解釋確實使它看起來像是在循環中開始的（這是不正確的）或者其他的東西......我真的沒有從中得到任何東西。至於這個笑話，我實際上已經採取了一套理論課程，每次教授_實際上都證明了這一點。你會問他任何一個有着衆所周知的解決方案的隨機集合論問題，他會立即向你念誦。真是荒謬的東西。 – rliu
啊當然可以。但是一旦烏龜到達環路，它們就不需要多次「k」步驟相交。事實上，它們總是需要少於「k」步才能相交。那麼，你的說法的重要性是什麼？它們在「k」步驟的多個步驟之後相交？ – rliu
陣列變爲，如你描述它，一個圖（更恰當地一個福雷斯特），其中每個頂點有出度恰好一個的。這種圖形的組成部分只能由可能以單個循環結束的鏈組成。也就是說，每個組分是形狀像一個O或像6。（我假定沒有指針是空的，但，這是容易處理。您與1型無循環的部件最終在所有。）
您可以通過「訪問」來跟蹤所有這些組件，並跟蹤您訪問「訪問」哈希或標誌數組的位置。
這是算法。
編輯它只是forrest的DFS簡化爲每個節點一個孩子的情況，這消除了堆棧（或遞歸）的需要，因爲不需要回溯。
Let A[0..N-1] be the array of pointers.
Let V[0..N-1] be an array of boolean "visited" flags, initially false.
Let C[0..N-1] be an array if integer counts, initially zero.
Let S[0..N-1] be an array of "step counts" for each component trace.
longest = 0 // length of longest cycle
for i in 0..N-1, increment C[j] if A[i] points to A[j]
for each k such that C[k] = 0
// No "in edges", so must be the start of a 6-shaped component
s = 0
while V[k] is false
V[k] = true
S[k] = s
s = s + 1
k index of the array location that A[k] points to
end
// Loop found. Length is s - S[k]
longest = max(longest, s - S[k])
end
// Rest of loops must be of the O variety
while there exists V[k] false
Let k be such that V[k] is false.
s = 0
while V[k] is false
V[k] = true
s = s + 1
k index of the array location that A[k] points to
end
// Found loop of length s
longest = max(longest, s)
end
空間與執行時間都正比於輸入陣列A的大小。如果您願意追蹤兩次6形組件，您可以擺脫S陣列。
加成我完全同意，如果它不是必要尋找最大尺寸的週期，那麼the ancient "two pointer" algorithm for finding cycles in a linked list優越，因爲它需要唯一不變的空間。
他實際上並未指定他想要最長的週期。 – hatchet
僞代碼示例？對於@hatchet所說的是的。 – NobleUplift
什麼是時間和空間的大O？從短暫的一瞥，它看起來像O（n^2）在時間上和O（n^2）在空間上，這是非常低效的。 – NobleUplift
使數組中的元素的有向圖，其中一個節點指向另一節點是否該結點到該節點的其指向與每個節點的元素的元素。跟蹤節點的indegree（指向它的指針的數目）。在創建圖形時，如果存在indegree == 2的節點，則該節點是無限循環的一部分。
如果第一元素被包括在無限循環，因此該算法開始之前，加入1個入度到所述第一元件以解決此上面失敗。
難道你只是通過指針，當你點擊一個與你的開始指針指向的元素相同的元素時，結束搜索並計算你所經歷的元素數量？ – Calpis
這些要點是否改變？或者從一開始就修正了這些要點？ –
總是有一個'循環'嗎？可以有零？會不止有一個？如果不止一個，你需要找到全部，還是隻有一個？ – hatchet