solution

本帖于 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

请您先登陆,再发跟帖!