似乎沒有那麽複雜

我再把想法寫清楚些，你看看是不是這樣：

這個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