新的N4哪天上架?# PDA - 掌中宝
c*t
1 楼
谁有那个帖子的link?好像那个帖子消失了。
好像是说给了一个整数array,有正数,有负数,要求把负数放在前面,正数放在后面,
同时保持顺序不变。
给个例子:
5 3 -2 9 -8 4 7 -10 6
结果应该是
-2 -8 -10 5 3 9 4 7 6
好像要求是O(n), in-place
大家讨论的结论是:
如果in-place,不可能O(n);
如果可以用额外的空间,可以很容易做到O(n).
有个人提到in-place,可以O(n logn),他没有说如何实现,这个如何做?我实在想不出
来。
我只能想出O(n^2) 的in-place的方法。
好像是说给了一个整数array,有正数,有负数,要求把负数放在前面,正数放在后面,
同时保持顺序不变。
给个例子:
5 3 -2 9 -8 4 7 -10 6
结果应该是
-2 -8 -10 5 3 9 4 7 6
好像要求是O(n), in-place
大家讨论的结论是:
如果in-place,不可能O(n);
如果可以用额外的空间,可以很容易做到O(n).
有个人提到in-place,可以O(n logn),他没有说如何实现,这个如何做?我实在想不出
来。
我只能想出O(n^2) 的in-place的方法。