你假设了所有的key都不一样

而康mm和乱弹没做这个假设。
在没有这个假设的情况下，难点在于当检查一个位置的时候怎样判断这个位置是否已经被移动过。比如假设这个序列只有0和1两种数，那你的程序对许多输入都得不到正确答案。
O(nlogn)的算法是比较容易得到的，比如可以divide and conquer。

所有跟帖： 

• 你能把不含此假设的题完整的写一遍么？ -说了就走- ♂ (355 bytes) () 08/09/2009 postreply 16:28:54

• 原题的假设够清楚了吧 -dynamic- ♂ (308 bytes) () 08/09/2009 postreply 17:26:12

• 我怎么理解的不一样 -说了就走- ♂ (60 bytes) () 08/09/2009 postreply 19:37:11

• 还不止是这种情况 -康mm- ♀ (91 bytes) () 08/09/2009 postreply 17:06:23

• 谢谢，明白你们说什么了 -说了就走- ♂ (118 bytes) () 08/09/2009 postreply 19:44:28