问一道题(2) - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>JobHunting - 待字闺中

问一道题(2)

问一道题(2)# JobHunting - 待字闺中

f*d2013-08-05 07:08

1 楼

将书组里的所有负数排在所有正数前面，保持正数和负数原来的相对顺序不变
inplace 时间复杂度越低越好~
eg
input
-5 2 -3 4 -8 -9 1 3 -10
output
-5 -3 -8 -9 -10 2 4 1 3

z*y2013-08-05 07:08

2 楼

有比 nlogn 快的么?

r*e2013-08-05 07:08

3 楼

quicksort partition

【在 f*********d 的大作中提到】

: 将书组里的所有负数排在所有正数前面，保持正数和负数原来的相对顺序不变
: inplace 时间复杂度越低越好~
: eg
: input
: -5 2 -3 4 -8 -9 1 3 -10
: output
: -5 -3 -8 -9 -10 2 4 1 3

f*d2013-08-05 07:08

4 楼

how？
每次找到最左边一个要换位的正数和最右边一个要换位的负数？
怎么二分做到？

【在 z***y 的大作中提到】

: 有比 nlogn 快的么?

f*d2013-08-05 07:08

5 楼

quick sort 是不稳定的
所以quick-sort partition似乎完不成~
可能我想错了~还请指出，

【在 r*******e 的大作中提到】

: quicksort partition

z*y2013-08-05 07:08

6 楼

void rev(vector &arr, int i, int j){
while(i < j){
int t = arr[i];
arr[i] = arr[j];
arr[j] = t;
i++;
j--;
}
return;
}
void Helper(vector &arr, int left, int right){
if(left == right) return;
int mid = left + (right-left)/2;
Helper(arr, left, mid);
Helper(arr, mid+1, right);
int i = mid, j = mid+1;
if(arr[i] < 0 || arr[j] > 0) return;
if(arr[i] <= 0 && arr[j] >= 0) return;
for(; i >= left && arr[i] >= 0; i--){}
for(; j <= right && arr[j] <= 0; j++){}
i++;
j--;
rev(arr, i, j);
rev(arr, i, i+j-mid-1);
rev(arr, i+j-mid, j);
return;
}
这个应该是 nlogn 的.

f*d2013-08-05 07:08

7 楼

感觉是对的~
可惜还是没看懂~
能稍微点拨一下嘛？
先谢啦！

【在 z***y 的大作中提到】

: void rev(vector &arr, int i, int j){
: while(i < j){
: int t = arr[i];
: arr[i] = arr[j];
: arr[j] = t;
: i++;
: j--;
: }
: return;
: }

z*y2013-08-05 07:08

8 楼

比如要处理下面的数列:
-3 -2 -4 1 4 -5 -2 -1 2 4
↑ ↑ ↑
i mid j
翻转(i,j)部分后变成
-3 -2 -4 -1 -2 -5 4 1 2 4;
↑ ↑
i j
再翻转两段
-3 -2 -4 -5 -2 -1 1 4 2 4.
Helper函数先循环调用两次, 把前半段和后半段都处理好.
然后只需把前半段的非负数和后半段的非正数处理好就行了.
三次翻转就可以了, 方法类似于把一篇文章以单词为单位头尾调换.

f*b2013-08-05 07:08

9 楼

re 单词为单位头尾调换

m*i2013-08-05 07:08

10 楼

mark

g*92013-08-05 07:08

11 楼

也贴个完整代码，序列shift移位的方法，把前一半的正数和后一半的负数对调但各自
顺序不变，
这个记得是编程珠玑的里的貌似。。
#include
#include
#include
#include
using namespace std;
void MySortImpl(vector &v, int b, int e) {
if (b >= e) {
return;
}
int m = (b + e) / 2;
MySortImpl(v, b, m);
MySortImpl(v, m+1, e);
int i, j;
i = m+1;
while (i-1 >= b && v[i-1] > 0) i--;
j = m;
while (j+1 <= e && v[j+1] < 0) j++;
int len1 = m - i + 1;
int len2 = j - (m+1) + 1;
int x, y;
for (x = i, y = j; x < y; x++, y--) {
std::swap(v[x], v[y]);
}
for (x = i, y = i+len2-1; x < y; x++, y--) {
std::swap(v[x], v[y]);
}
for (x = i+len2, y = i+len1+len2-1; x < y; x++, y--) {
std::swap(v[x], v[y]);
}
return;
}
void MySort(vector &v) {
int n = v.size();
MySortImpl(v, 0, n-1);
}
void Test() {
int a[] = {-5, 2, -3, 4, -8, -9, 1, 3, -10};
vector v(a, a+sizeof(a)/sizeof(int));
MySort(v);
copy(v.begin(), v.end(), ostream_iterator(cout, " "));
cout << endl;
}
int main() {
Test();
return 0;
}

f*d2013-08-05 07:08

12 楼

wow, 这是实在是精巧~多谢指点了！
二分会用，翻转的也会用，合在一起就傻眼了，
顿时发现，二分也不会用，翻转也还没掌握~

【在 z***y 的大作中提到】

: 比如要处理下面的数列:
: -3 -2 -4 1 4 -5 -2 -1 2 4
: ↑ ↑ ↑
: i mid j
: 翻转(i,j)部分后变成
: -3 -2 -4 -1 -2 -5 4 1 2 4;
: ↑ ↑
: i j
: 再翻转两段
: -3 -2 -4 -5 -2 -1 1 4 2 4.

f*d2013-08-05 07:08

13 楼

NICE CODE~ MARK

【在 g***9 的大作中提到】

: 也贴个完整代码，序列shift移位的方法，把前一半的正数和后一半的负数对调但各自
: 顺序不变，
: 这个记得是编程珠玑的里的貌似。。
: #include
: #include
: #include
: #include
: using namespace std;
: void MySortImpl(vector &v, int b, int e) {
: if (b >= e) {