原题的假设够清楚了吧

来源: 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

请您先登陆，再发跟帖！