这题有一些不同的做法,这里提供一种:
首先把这个数组看成一个有向图:如果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从原处开始,同样的速度前进。它们相遇的地方就是我们要的数。
solution
所有跟帖:
•
hmmm,佩服. "形状像一个勺子", haha...
-戏雨飞鹰-
♀
(0 bytes)
()
05/21/2009 postreply
12:25:03
•
这个题目曾是微软的面试题目。但是没有了数组'read only'的条件,
-戏雨飞鹰-
♀
(75 bytes)
()
05/21/2009 postreply
13:12:13