原題的假設夠清楚了吧

來源: dynamic 於 2009-08-09 17:26:12 [] [舊帖] [給我悄悄話] 閱讀數 : (308 bytes)
回答: 你假設了所有的key都不一樣 由 dynamic 於 2009-08-08 15:58:51

給出一個數列
a[1],a[2],a[3],...,a[2n]
其中a[i]可以是任意值，可以重複也可以不重複。

要求用const auxiliary memory和linear time，把數組變成
a[1],a[3],...,a[2n-1],a[2],a[4],...,a[2n]

我隻是說O(nlogn) time + O(1) memory比較容易辦到，沒說這樣解決了原問題。顯然O(n)+O(1)並不是容易的事情。

所有跟帖： 

• 我怎麽理解的不一樣 -說了就走- ♂ 給 說了就走 發送悄悄話 說了就走 的博客首頁 (60 bytes) () 08/09/2009 postreply 19:37:11

請您先登陸，再發跟帖！