投递文章投递文章 投稿指南 RSS订阅RSS订阅

算法面试题——两道百度笔试题

来源:IT堂 堂友 发布时间:2011-09-01 收藏 投稿 字体:【

   今天看到一位园友写了一篇关于百度的面试题的博客,成了评论头条,再下看了一下,非常感兴趣,那位博主的算法能力跟我一样需要提高,估计他的功力还在我之下,所以再下不才,在这里把自己的源码贴出来。

         百度面试题(一):假设一整型数组存在若干正数和负数,现在通过某种算法使得该数组的所有负数在正数的左边,且保证负数和正数间元素相对位置不变。时空复杂度要求分别为: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();
return 0;
}

运行结构截图:

顶一下
(113)
99.1%
踩一下
(1)
0.9%
本文Tags:
  • 表情:
  •    
  • 评价:
用户名: 密码: 匿名 注册
最新评论 查看所有评论
About iTtang - 联系我们  - 专题列表 - 友情链接  -  高级搜索  -  帮助中心  -  您的意见