it takes a bit more than that

there are some issues with your method:

1. starting with a[i] != i, you might find a cycle and go back to i. In this cycle, no element occurred more than once.

2. The problem asks you to find one repeated element. Not every element in a cycle is repeated. Finding the exact "entrance" to a cycle is the tricky part of the problem.

The big idea is correct though, and there is a linear time algorithm. Good luck~

所有跟帖： 

• hmm，这个有意思：） -戏雨飞鹰- ♀ (0 bytes) () 05/18/2009 postreply 21:12:19

• 回复：it takes a bit more than that -utopian- ♂ (51 bytes) () 05/20/2009 postreply 17:23:11

• hashing needs linear memory as well. we want constant memory her -dynamic- ♂ (0 bytes) () 05/20/2009 postreply 17:28:12

• Pay attention to some key numbers. -乱弹- ♂ (0 bytes) () 05/20/2009 postreply 19:24:24

• 觉得在哪里见过这个题目 -haha2000- ♂ (19 bytes) () 05/21/2009 postreply 07:24:10

• I don't think so. -乱弹- ♂ (0 bytes) () 05/21/2009 postreply 09:52:29

• 这题目是IMB ２００４ 一月的一个puzzle：） -戏雨飞鹰- ♀ (79 bytes) () 05/21/2009 postreply 12:22:12

• Yes, right! thanks! -haha2000- ♂ (0 bytes) () 05/22/2009 postreply 11:05:23