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

来源: 2009-08-08 15:58:51 [旧帖] [给我悄悄话] 本文已被阅读:

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