似乎没有那么复杂

我再把想法写清楚些，你看看是不是这样：

这个array是a[1],a[2],...,a[n].假设一开始a[k]=k，目的是通过常数个变量和O(n)时间让a[k]=f(k).这里f(k)是某个一一对应函数。

假设f(k)及其反函数g(k) (对任何k=1,2,...n都有f(g(k))=g(f(k))=1)都可以通过O(1)的计算得出。如果这点不成立，肯定没有O(n)的算法（假设在大于1的循环中的数有O(n)个）

下面的大致算法：

for(k=1;k {
if(a[k]==f(k)) continue; //该数（以及所在的循环）已经满足条件了
//不符合条件的k是某个循环里第一个（最小的）不正确的数
for(t=k;f(t)!=k;t=f(t))
{
a[t]=f(t);
}
a[t]=k;
//经过这个操作，k所在的循环的所有数字都到了最终要求的位置。
}

除了个数为1的循环，所有循环都被置换一次，也就是任何一个k都只被置换一次。每个置换之前有一个O(1)的判断，所以总数还是O(n)，而变量只有两个。

所有跟帖： 

• 回复：似乎没有那么复杂 -康MM- ♀ (104 bytes) () 07/30/2009 postreply 07:33:36

• 我觉得我解释不清楚 -说了就走- ♂ (1593 bytes) () 07/30/2009 postreply 11:56:00

• 主要是难以判断一个位置有没有排好。 -乱弹- ♂ (355 bytes) () 07/30/2009 postreply 17:30:25

• 你可以run一下这个程序，对任何n都适用 -说了就走- ♂ (357 bytes) () 07/30/2009 postreply 20:47:50

• 你一直在假设a[k]=k。没有这个假设你的算法不成立 -康MM- ♀ (0 bytes) () 07/31/2009 postreply 07:14:51

• 那么请问你的假设是什么？ -说了就走- ♂ (216 bytes) () 07/31/2009 postreply 18:16:46

• 还是问冬瓜太郎吧，他说可以就可以 -康MM- ♀ (177 bytes) () 08/02/2009 postreply 10:25:52

• 你说得很有道理 -说了就走- ♂ (2675 bytes) () 08/02/2009 postreply 13:50:02

• 我还是觉得我们在说两件不同的事 -康MM- ♀ (0 bytes) () 08/06/2009 postreply 17:49:24