o*****e
发帖数: 99 | 1 Given a set of positive and negative integers group all the positive
integers on one side and negative integers on one side...
numbers should be in the same order they appear....
Any O(N) algorithm without using extra space? |
d*****t
发帖数: 41 | |
d*****t
发帖数: 41 | 3 void group(int* a, int length)
{
int i=0;
int j= length-1;
while(i
{
while(a[i]<0)
i++;
while(a[j]>0)
j--;
if(i
{
swap(a[i], a[j]);
j--;
i++;
}
}
} |
o*****e
发帖数: 99 | 4 quicksort doesn't work here.
"numbers should be in the same order they appear"
【在 d*****t 的大作中提到】
: void group(int* a, int length)
: {
: int i=0;
: int j= length-1;
: while(i: {
: while(a[i]<0)
: i++;
: while(a[j]>0)
: j--;
|
h**********d
发帖数: 4313 | 5 这样可以吗？
先数一下positive 的个数m
然后两个指针i, j分别从0 和 m开始，i 如果碰到负数就和 j 碰到的第一个正数对调，直
到走完
【在 o*****e 的大作中提到】
: Given a set of positive and negative integers group all the positive
: integers on one side and negative integers on one side...
: numbers should be in the same order they appear....
: Any O(N) algorithm without using extra space?
|
c*******t
发帖数: 1095 | |
h**********d
发帖数: 4313 | 7 是，刚才把程序写了一下，顺序还是有问题
【在 c*******t 的大作中提到】
: 只想到用链表可以实现，用数组还没想出来
|
