solution

這題有一些不同的做法，這裏提供一種：

首先把這個數組看成一個有向圖：如果a[i]=j，那麽就加一條從i到j的邊。不難發現，每個點的out-degree都是1。

如果從n+1這個點出發，那麽我們會進入一個cycle，並且這個cycle不含n+1（形狀像一個勺子，或者說希臘字母rho）。那個cycle的"entrance"就至少被兩個數指向，所以我們就隻需要找到那個entrance。

先從n+1出發，走n步，此時肯定已經進入cycle了。記錄下此時位置，看繼續多少步後回到原處，就求出了cycle的長度k。

然後重新回到n+1。讓一個pointer先走k步，另一個pointer從原處開始，同樣的速度前進。它們相遇的地方就是我們要的數。

所有跟帖： 

• hmmm，佩服. "形狀像一個勺子", haha... -戲雨飛鷹- ♀ (0 bytes) () 05/21/2009 postreply 12:25:03

• 這個題目曾是微軟的麵試題目。但是沒有了數組'read only'的條件， -戲雨飛鷹- ♀ (75 bytes) () 05/21/2009 postreply 13:12:13