一个面试题
百度面试题，假设一整型数组存在若干正数和负数，现在通过某种算法使得该数组的所有负数在正数的左边，且保证负数件和正数间元素相对位置不变。时空复杂度要求分别为：o(n),o(1)
例如
-3 4 2 -1 7 3 -5
排序后
-3 -1 -5 4 2 7 3

[解决办法]
之前有个Sleep排序，不知能不能用上
[解决办法]
冒泡排序。。。
[解决办法]
//使用快速排序的思想。用0来进行partition。下面是我写的代码

#include <iostream>
using namespace std;

void exchange(int& a,int& b){
int temp;
temp = a;
a = b;
b = temp;
}

int partition(int *a,int p,int r){
int q;
int temp;
int i,j;
i=p-1;
for(j=p;j<=r;j++){
if(a[j] < 0){
i++;
exchange(a[i],a[j]);
}
}
return 1;
}

int main(){
int a[10] = {1,9,12,-1,7,6,-2,8,11,3};
for(int i=0;i<10;i++){
cout << a[i] << " ";
}
cout << endl;
partition(a,0,9);
for(int i=0;i<10;i++){
cout << a[i] << " ";
}
}

[解决办法]

整型数组换成链表处理就行了。
[解决办法]
等待答案
[解决办法]
中间的有个sleepa
[解决办法]
链表：
一个原链表，一个新链表，分别存储正、负数
在原链表中顺序查找，找到一个负数则摘除、链入新链表，直到原链表尾。
将原链表链到新链表后
－－完毕
[解决办法]
直接顺序遍历。搞两个指针，一个负数一个正数。 满足，负数指针大于正数指针就交换，

应该就满足题目要求了。
[解决办法]
看不到我的回复吗？那我再发一遍好了。就是使用快速排序的思想。用0作为partition的条件。步骤为：
从头开始遍历，然后发现某一个数比0小，就把它换到前面。当然前面也有一个记录边界位置的变量。代码如下：

#include <iostream>
using namespace std;

void exchange(int& a,int& b){
int temp;
temp = a;
a = b;
b = temp;
}

int partition(int *a,int p,int r){
int q;
int temp;
int i,j;
i=p-1;
for(j=p;j<=r;j++){
if(a[j] < 0){
i++;
exchange(a[i],a[j]);
}
}
return 1;
}

int main(){
int a[10] = {1,9,12,-1,7,6,-2,8,11,3};
for(int i=0;i<10;i++){
cout << a[i] << " ";
}
cout << endl;
partition(a,0,9);
for(int i=0;i<10;i++){
cout << a[i] << " ";
}
}

[解决办法]

C/C++ code

void my_func(int src[], int size)                    {                                                        int *table = new int [size];                         int i, j;                                            int *p;                                                                                                   for (p = table, i= 0; i < size; ++i)                 {                                                        if (src[i] < 0)                                      {                                                        *p++ = src[i];                                   }                                                }                                                                                                                                                              for (p = table + size, j = size - 1; j >= 0; --j)    {                                                        if (src[j] >= 0)                                     {                                                        *--p = src[j];                                   }                                                }                                                                                                         for (i = 0; i < size; ++i)                           {                                                        src[i] = table[i];                               }                                                                                                         delete[] table;                                  }
[解决办法]
探讨


C/C++ code

void my_func(int src[], int size)                    
{                                                    
    int *table = new int [size];                     
    int i, j;           ……

[解决办法]
探讨

引用:

C/C++ code

void my_func(int src[], int size)
{
int *table = new int [size];
int i, j; ……

空间复杂度要求是O(1)！

[解决办法]
我叻个去，能这么简单嘛。。只要求空间复杂度，对时间木有要求。
我说下思想，
空间复杂度o(n)的话，定义一个同样大小的数组，遍历2遍，第一遍把负数一个个弄进来，第二遍你懂的。
O(1)的话，int tmp；
设置当前位置为数组首位。
1.当前位置开始找正数,找到跳2，没找到退出。
2.从当前位置找负数，找到跳3，没找到退出。
3.找到的正负数调换位置，跳1。
[解决办法]
只能用常数个变量，3个5个10个都行，但不能是n的现行函数个
[解决办法]
汗，还真是。只考虑了一面的。是我考虑不周了~

探讨

引用:

引用:
引用:

看不到我的回复吗？那我再发一遍好了。就是使用快速排序的思想。用0作为partition的条件。步骤为：
从头开始遍历，然后发现某一个数比0小，就把它换到前面。当然前面也有一个记录边界位置的变量。代码如下：

#include <i……

[解决办法]
O(1)就是空间是一个常数，
O(n)就是空间和n是线性相关的，比如n的倍数。
探讨

引用:
引用:

C/C++ code

void my_func(int src[], int size) 
 
{
int *table = new int [size];
int i, j; ……

空间复杂度要求是O(1)！

谢谢提醒，
我不是很清楚O(1)复杂度是什么意思，是只能用一个变量……