f*********d
发帖数: 140 | 1 将书组里的所有负数排在所有正数前面，保持正数和负数原来的相对顺序不变
inplace 时间复杂度越低越好~
eg
input
-5 2 -3 4 -8 -9 1 3 -10
output
-5 -3 -8 -9 -10 2 4 1 3 | z***y
发帖数: 50 | | r*******e
发帖数: 7583 | 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*********d
发帖数: 140 | 4 how？
每次找到最左边一个要换位的正数和最右边一个要换位的负数？
怎么二分做到？
【在 z***y 的大作中提到】
: 有比 nlogn 快的么?
| f*********d
发帖数: 140 | 5 quick sort 是不稳定的
所以quick-sort partition似乎完不成~
可能我想错了~还请指出，
【在 r*******e 的大作中提到】
: quicksort partition
| z***y
发帖数: 50 | 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*********d
发帖数: 140 | 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***y
发帖数: 50 | 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*******b
发帖数: 520 | | m****i
发帖数: 650 | | g***9
发帖数: 159 | 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*********d
发帖数: 140 | 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*********d
发帖数: 140 | 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) {
|
|
