- 浏览: 61874 次
- 性别:
- 来自: 北京
最新评论
百度笔试算法题一道。
- 博客分类:
- 笔试
一个数组a[0-n-1],a[0-mid]和a[mid+1-n-1]是各自升序的,现在要把a[0-n-1]排成有序的。要求空间复杂度o(1),时间复杂度尽量低。
我想到的方法就是将后面序列的每个元素对前面序列进行插入排序。搜索插入位置的时候考虑从上一个插入元素位置之后开始搜索。
说明一下这个方法时间复杂度最坏应该是o(n^2),网上有o(n)解法。
我想到的方法就是将后面序列的每个元素对前面序列进行插入排序。搜索插入位置的时候考虑从上一个插入元素位置之后开始搜索。
说明一下这个方法时间复杂度最坏应该是o(n^2),网上有o(n)解法。
#include <stdlib.h> int insert(int* a, int begin, int end, int x){ int pos = end; //插入位置 int last = a[end]; int exchange = 0; int i; //寻找插入位置 for(i = begin; i <= end; i++){ if(a[i] > x){ pos = i; exchange = 1; break; } } if(exchange){ //移动元素 for(i = end; i > pos; i--){ a[i] = a[i-1]; } a[end+1] = last; a[pos] = x; }else{ pos = end+1; } return pos; } void print_r(int* a, int n){ int i = 0; while(i<n){ printf("%d\t",a[i++]); } printf("\n"); } void merge(int* a, int n, int mid){ int search_begin = 0; int i; for(i = mid; i < n; i++){ search_begin = insert(a,search_begin, i, a[i+1]); } } int main(){ int a[10] = { 1,2,3,7,9,0,4,10,18,20 }; int mid = 4; merge(a,10,mid); print_r(a,10); return 0; }
发表评论
-
求链表中间节点的值,检测链表的环
2012-07-27 14:19 806求链表中间节点的值,检测链表的环 int loop(st ... -
实习前记
2012-07-16 15:27 696经过回来一周的找工作,总体感觉就是很累啊,每天东跑西颠的。面了 ... -
php函数参数列表
2012-05-11 16:50 1400[size=medium] 1.直接传值 function ... -
php的ob_flush和flush
2012-05-10 21:20 1069php.ini中 output_buffering = of ... -
php读文件的4中方法。
2012-05-10 20:38 871fopen $fp = fopen("downl ... -
自己实现php UTF8中文字符串截取
2012-05-09 11:38 2848header("Content-type: te ... -
C与C++动态分配,释放内存的区别
2012-05-08 17:30 160221. malloc()函数 1.1 malloc的 ... -
nginx rewrite
2012-05-04 11:23 0http://blog.cafeneko.info/2010/ ... -
php magic method
2012-05-04 11:16 859php的魔术方法总结 php的魔术方法都是和类有关的。 ... -
诡异的 shell 08 bug
2012-04-30 01:11 724v=08 echo $v shell里以0开头的都会把它当作8 ... -
排序相关
2012-04-22 16:01 0排序分类 内排序: 交换式排序: ... -
php string
2012-04-22 11:33 853一.字符串类型 php一共有8中数据类型 ... -
简单的树的递归、非递归创建,前序中序后序遍历
2012-04-21 10:03 1034c语言写着还挺带感 #in ... -
php 深度优先递归输出路径下所有文件
2012-04-19 21:27 1491<?php $dir = " ... -
简单的栈
2012-04-19 21:14 679#include <stdio.h> #de ... -
简单的循环队列
2012-04-19 21:13 780#include <stdlib.h> ... -
单链表删除一个节点
2012-04-19 21:10 9813有头结点的情况,附加一个逆置 #include <s ... -
KMP与BF,实现了一个非主流next函数
2012-04-19 20:16 899#include <stdlib.h> #i ... -
ip过滤问题
2012-03-22 21:09 0假设有很多段ip段属于教育网的,如何尽快辨别一用户ip是否属于 ... -
求三叉树高度
2012-03-18 17:05 3053有12345个结点的满3叉数的高度为_____写出计算过程 ...
相关推荐
华为OD、大厂笔试算法题; 一共87题,每一题附答案(java语言),笔试时频繁出现的原题,想进大厂的小伙伴,欢迎下载; eg: 1、5键键盘的输出 有一个特殊的5键键盘,上面有a,ctrl-c,ctrl-x,ctrl-v,ctrl-a五个键...
vue双向绑定原理,面试时自己拿来看的代码
部分IT公司笔试算法题,比较有用,让大家学习,很多有名算法!
C++面试题笔试题C++ 数据结构算法笔试题资料合集: 50个C、C++面试题.pdf C++ 数据结构、算法笔试题.docx C++基础面试题.docx C++开发工程师面试题库.docx C++技能测试试卷一及答案.docx C++技能测试试卷二及答案....
求职招聘_2014去哪儿网校园招聘笔试算法题汇总.docx求职招聘_2014去哪儿网校园招聘笔试算法题汇总.docx求职招聘_2014去哪儿网校园招聘笔试算法题汇总.docx求职招聘_2014去哪儿网校园招聘笔试算法题汇总.docx求职招聘...
兔子繁殖 半段质数 水仙花数 最大公约数 最小公倍数 数字排序等经典的编程问题
百度笔试题 百度 笔试题 百度 笔试题
百度笔试题百度笔试题百度笔试题百度笔试题百度笔试题百度笔试题
算法笔试题算法笔试题算法笔试题算法笔试题算法笔试题算法笔试题算法笔试题算法笔试题算法笔试题算法笔试题算法笔试题算法笔试题算法笔试题算法笔试题算法笔试题
百度笔试题大全 百度笔试题大全 百度笔试题大全 百度笔试题大全 百度笔试题大全
百度_新浪_盛大2011年面试笔试算法题收集(含答案)_java
12-02-28网易笔试一道算法题,附件代码是我自己的解题
超多IT公司笔试算法题及具体答案……
全排序、二分查找、冒泡排序、阶乘、最大公约数、最小公倍数、...这是里面包含的算法,本人在准备笔试的时候找的,算法尽量采用最优的。 所有的代码均经过测试,个人觉得没有问题,如果哪位大牛找到错误,欢迎批评指正
华为校园招聘笔试算法题汇总.doc
2014华为校园招聘笔试算法题汇总.docx2014华为校园招聘笔试算法题汇总.docx2014华为校园招聘笔试算法题汇总.docx2014华为校园招聘笔试算法题汇总.docx2014华为校园招聘笔试算法题汇总.docx2014华为校园招聘笔试算法...
百度历年笔试题百度历年笔试题百度历年笔试题百度历年笔试题
IT公司笔试算法题 面试 笔试 经典体型。可以改。 非常使用。算法。数据结构
java笔试算法题及答案.doc java笔试算法题及答案.doc