Microsoft : Rearrange an array of positive and negative integers,

lambda2fei 发表于 2012-9-10 13:19
汗。。。还有个BUT没看到。。。。那不能快排了。。用归并吧，stl源码的归并排有个参数是可用buffer的大小 ...

是挺难搞的 前几天在网上看到大牛用 O(1) 空间 O(n) 时间做的
我在 6 楼贴了链接

BinaryWitch 发表于 2012-9-11 10:16
是挺难搞的 前几天在网上看到大牛用 O(1) 空间 O(n) 时间做的
我在 6 楼贴了链接

我可以很负责任地告诉你，这个方法是的复杂度绝对不是O(n)。否则按照他这么搞，快速排序早就变成稳定排序了。

lambda2fei 发表于 2012-9-11 12:56
我可以很负责任地告诉你，这个方法是的复杂度绝对不是O(n)。否则按照他这么搞，快速排序早就变成稳定排序 ...

哪里有问题呢？

题目要求没有说要sorting吧，只是re-arrange
所以不要拿NlongN的排序说事儿咯
而且BUT条件也表示不能用用排序来做