can be done in linear time...

来源: 于 2009-05-18 19:42:41 [旧帖] [给我悄悄话] 本文已被阅读：次

find i such that a[i] != i

Let us assume i = 1

a[1], a[a[1]], ..., a^{n}[1] can be viewed as a single linked list...

2x chase...