solution

来源: dynamic 于 2009-05-20 21:41:18 [] [旧帖] [给我悄悄话] 阅读数 : (572 bytes)
本帖于 2009-06-09 09:31:02 时间, 由普通用户 康MM 编辑
回答: Loop in single linked list 由 外-国人 于 2009-05-15 07:55:51

这题有一些不同的做法，这里提供一种：

首先把这个数组看成一个有向图：如果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

请您先登陆，再发跟帖！