百度算法笔试题02

 

   百度面试题（一）：假设一整型数组存在若干正数和负数，现在通过某种算法使得该数组的所有负数在正数的左边，且保证负数和正数间元素相对位置不变。时空复杂度要求分别为：o(n)和o(1)。

         其实开始的时候我也是一头雾水，在纸上画画之后发现，其实就是一道变形的插入排序。幸运的是这里不需要比较大小，要比较大小的话时间复杂度是O(n2),只用判断正负，那时间复杂度就只要O(n)了。

         如：-3,1,2，-1，-3,4。其实就是把正数后面的第一个负数（如-1）插到第一个正数(1)的前面，负数之间的每个正数(1,2)后移一位，就这么简单。时间复杂度刚好为O(n),控件复杂度为O(1)。

　　

//算法分开正负数
void insertSort(int*A ,int size)
{ 
int minus=-1,plus=-1;
int tmp=0;
for(int i=0;i<size;i++)
    {
if(minus==-1)
        {
if(A[i]<0&& plus>=0)
            {
                minus=i;
            }

if(A[i]>0&& plus<0)
            {
                plus=i;
            }
        }

if(minus>=0&& plus>=0)
        {
            tmp=A[plus];
            A[plus++] = A[minus];
for (int k = minus; k> plus; k--) 
            {
                 A[k] = A[k -1];
            }
            A[plus]=tmp;
            minus=-1;
        }
    }
}

 

 

 

 

         百度面试题（二），给定一个存放正数的数组，重新排列数组使得数组左边为奇数，右边为偶数，且保证奇数和偶数之间元素相对位置不变。时空复杂度要求分别为：o(n)和o(1)。

       其实这两道笔试题没有什么区别，要说有区别就是看你是否理解。

 

//算法分开奇偶数
void insertSort1(int*A ,int size)
{ 
int minus=-1,plus=-1;
int tmp=0;
for(int i=0;i<size;i++)
    {
if(minus==-1)
        {
if(A[i]%2!=0&& plus>=0)
            {
                minus=i;
            }

if(A[i]%2==0&& plus<0)
            {
                plus=i;
            }
        }

if(minus>=0&& plus>=0)
        {
            tmp=A[plus];
            A[plus++] = A[minus];
for (int k = minus; k> plus; k--) 
            {
                 A[k] = A[k -1];
            }
            A[plus]=tmp;
            minus=-1;
        }
    }
}

 

 

 

 

测试代码如下：

//测试代码
int main() {

int A[]={2,1,-2,12,4,-2,-4,-6 };
int size=sizeof(A)/sizeof(int);
    cout<<"-----------------------算法分开正负数-----------------------"<<endl;
for(int i=0;i<size;i++)
    {
        cout<<A[i]<<"\t";
    }
    cout<<endl;
    insertSort(A,size);
for(int i=0;i<size;i++)
    {
        cout<<A[i]<<"\t";
    }
    cout<<endl;
    cout<<endl;
cout<<"-----------------------算法分开奇偶数-----------------------"<<endl;
int B[]={2,1,-2,12,4,-2,-4,-6};
int s=sizeof(B)/sizeof(int);
for(int i=0;i<s;i++)
    {
        cout<<B[i]<<"\t";
    }
    cout<<endl;
    insertSort1(B,s);
for(int i=0;i<s;i++)
    {
        cout<<B[i]<<"\t";
    }

    getchar();
return0;
} 

运行结构截图：