計數數組索引

Question

如果我有數字等[5，2,3，2,0，2]

我要計數我可以連續索引的陣列，直到我們走到了的次數的陣列指數我們已經參觀，像這樣：

A[0] = 5 
A[5] = 2 
A[2] = 3 
A[3] = 2 stop here because we already indexed 2. 

所以我的問題是：在不使用額外的數據結構來存儲先前訪問的指標，是有辦法，我可以告訴我的程序何時停止索引？

Answer 1

看樣子您將該數組視爲有向圖。如果是這樣，那麼你真正要求的是如何在有向圖中檢測週期。

參見：

• Best algorithm for detecting cycles in a directed graph
• Find all paths with cycles in directed graph, given the source vertex
• How to detect if a directed graph is cyclic?

要明確雖然回答你的問題：如果你是在一個迷宮周圍徘徊，你怎麼告訴你，如果」以前去過特定路口嗎？您可能會考慮放棄麪包屑或解開線程來提醒您自己去過哪裏。這裏是一樣的東西。您需要用「已訪問」標記註釋原始數組，或者保留您訪問過的索引的副本。

Answer 2

如果你在開始時初始化爲無效值的數組元素，比如-1，那麼你就可以停止，如果一個數組元素已指定，如下面的僞代碼：

​​