昨天陪同学在北大,发现百度在笔试招实习生,现场笔试。顺道也霸笔了一把。有这样一道小题,一个数组a, a[0,1....mid-1]是有序的,a[mid,.....num]也是有序的,现在要把这两部进行merge,如何在空间复杂度为0(1)的情况下进行合并,使得a整体有序。a[i]支持<运算。
下边是我的一个算法的实现:
public static void main(String[] args) {
int a[]={2,3,6,10,23,39 ,1,4,5,7,8,9,100 };
test(a,6);
}
public static void test(int a[],int mid){
int tmp;
int p;
for(int i=0;i<mid;i++){
p=mid;
if(a[p]<a[i]){
tmp=a[i];
a[i]=a[p];
a[p]=tmp;
for(int j=mid+1;j<a.length;j++){
if(a[j]<a[p]){
tmp=a[j];
a[j]=a[p];
a[p]=tmp;
p++;
}else{
break;
}
}
}
}
for(int k=0;k<a.length;k++){
System.out.println(a[k]);
}
}
这里的tmp是所谓的 空间复杂度,仅仅用到了一个中间变量。思路是:仅仅需要遍历前半部分,同时去比较后半部分的第一个元素,在比较的过程中,如果出现了有较小的值,就去互换,同时让后半部分保持有序。效率可能不是最好的。这个题目算是比较基础的。
分享到:
相关推荐
C++面试题笔试题C++ 数据结构算法笔试题资料合集: 50个C、C++面试题.pdf C++ 数据结构、算法笔试题.docx C++基础面试题.docx C++开发工程师面试题库.docx C++技能测试试卷一及答案.docx C++技能测试试卷二及答案....
算法笔试题算法笔试题算法笔试题算法笔试题算法笔试题算法笔试题算法笔试题算法笔试题算法笔试题算法笔试题算法笔试题算法笔试题算法笔试题算法笔试题算法笔试题
该资源为2019年雷达算法工程师笔试题,包含单选,多选,判断和问答题。推荐需要应聘雷达算法岗的同学可以下载。
大疆求职算法笔试题 大疆求职算法笔试题大疆求职算法笔试题大疆求职算法笔试题大疆求职算法笔试题大疆求职算法笔试题大疆求职算法笔试题
不骗人,整理的一套试卷的全部题目~2017年哒
华为OD、大厂笔试算法题; 一共87题,每一题附答案(java语言),笔试时频繁出现的原题,想进大厂的小伙伴,欢迎下载; eg: 1、5键键盘的输出 有一个特殊的5键键盘,上面有a,ctrl-c,ctrl-x,ctrl-v,ctrl-a五个键...
百度校园招聘笔试试题-深度学习算法研发工程师.docx百度校园招聘笔试试题-深度学习算法研发工程师.docx百度校园招聘笔试试题-深度学习算法研发工程师.docx百度校园招聘笔试试题-深度学习算法研发工程师.docx百度校园...
北京-百度计算机视觉算法工程师笔试-回忆版.pdf
12-02-28网易笔试一道算法题,附件代码是我自己的解题
兔子繁殖 半段质数 水仙花数 最大公约数 最小公倍数 数字排序等经典的编程问题
阿里巴巴最新算法工程师笔试题.pdf
各大软件公司面试--算法笔试题各大软件公司面试--算法笔试题
软件开发中常用算法笔试题 1、将一个字符串逆序 2、将一个链表逆序 。。。。
常见算法笔试或面试题,有些题目还挺有趣.
百度校园招聘笔试面试题22个文档资料合集: 百度2010-2011年各部门招聘笔试题及面经总结.doc 百度2014校园招聘笔试试题-产品经理笔试题.doc 百度2014校园招聘笔试试题-北京站未知...百度笔试题面试题集总(总81页).docx
2014年大华笔试题目,和以往2012、2013笔试题目出入很大,备考利器啊!
全排序、二分查找、冒泡排序、阶乘、最大公约数、最小公倍数、...这是里面包含的算法,本人在准备笔试的时候找的,算法尽量采用最优的。 所有的代码均经过测试,个人觉得没有问题,如果哪位大牛找到错误,欢迎批评指正
算法笔试题 有答案 笔试题 有答案 有答案
数据结构与算法笔试题考点分析.doc
vivo2019校招图像算法工程师笔试题