百度面试题(一):假设一整型数组存在若干正数和负数,现在通过某种算法使得该数组的所有负数在正数的左边,且保证负数和正数间元素相对位置不变。时空复杂度要求分别为: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;
}
运行结构截图:
分享到:
相关推荐
大疆求职算法笔试题 大疆求职算法笔试题大疆求职算法笔试题大疆求职算法笔试题大疆求职算法笔试题大疆求职算法笔试题大疆求职算法笔试题
百度校园招聘笔试试题-深度学习算法研发工程师.docx百度校园招聘笔试试题-深度学习算法研发工程师.docx百度校园招聘笔试试题-深度学习算法研发工程师.docx百度校园招聘笔试试题-深度学习算法研发工程师.docx百度校园...
北京-百度计算机视觉算法工程师笔试-回忆版.pdf
百度 2014校园招聘笔试试题--深度学习算法研发工程师.docx百度 2014校园招聘笔试试题--深度学习算法研发工程师.docx百度 2014校园招聘笔试试题--深度学习算法研发工程师.docx百度 2014校园招聘笔试试题--深度学习...
百度历年笔试试题汇总 技术类笔试试题 算法 数据结构等
百度公司两年来的笔试题,快来看啊
百度2014校园招聘笔试试题-研发工程师笔试题.docx
百度技术研发笔试题,涉及数据结构及相关算法,哈希等知识
百度网上笔试题及答案 用C语言实现一个revert函数,它的功能是将输入的字符串在原串上倒序后返回。 2 编程: 用C语言实现函数void * memmove(void *dest,const void *src,size_t n)。memmove函数的功能是拷贝src...
百度2010-2011年各部门招聘笔试题及面经总结.doc 百度2014校园招聘笔试试题-产品经理笔试题.doc 百度2014校园招聘笔试试题-北京站未知岗位.docx 百度2014校园招聘笔试试题-南京PC客户端开发笔试题.doc 百度2014校园...
百度笔试题 汉略曾考的测试题目 16道C语言面试题例子 死循环(Infinite loops) 数据声明(Data declarations) 位操作(Bit manipulation) 访问固定的内存位置(Accessing fixed memory locations) 中断...
百度的面试题,招聘iOS开发工程师,解答详细.
算法面试100题全部答案集锦.pdf搜狐2013校招笔试题.pdf搜狗2015校园招聘研发类笔试题.pdf浙江大华2015届校园招聘算法、软件类笔试题.pdf百度2015产品经理.pdf百度2015前端研发笔试卷.pdf百度2015大数据云计算研发笔...
2015校园招聘笔试题大合集,汇集百度、腾讯、阿里等多家大型互联网企业的面试题,非常具有参考价值。 内容包括: 360校园招聘2015届技术类笔试题.pdf ... 浙江大华2015届校园招聘算法、软件类笔试题.pdf
百度面试必备笔试试题。.../*百度面试题算法: 1。将集合按照大小从小到大排序,组成待处理的集合列表。 2。取出待处理集合列表中最小的集合,对于集合的每个元素,依次在其他集合中搜索 是否有此元素存在:
百度_新浪_盛大2011年面试笔试算法题收集(含答案)_java
百度的笔试题目,2010年的,注重算法,祝大家好运啊
2015创新工场校招研发笔试题.pdf 2015小米校招技术类笔试题.pdf 360校园招聘2015届技术类笔试题.pdf 4399游戏2015校园招聘游戏开发类笔试题.pdf 人人网2015研发笔试卷B.pdf 人人网2015研发笔试卷C.pdf 搜狗2015校园...
2011年9月24日百度成都笔试题回忆,研发类通用试卷
2012十月下旬腾讯,网易游戏,百度最新校园招聘笔试题集锦