首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
输入一个按升序排序过的整数数组{1、2、4、7、11、15}以及一个整数数字15,可以从该数组中找到两个数字,即4和11,使得4+11=15。请实现一个时间上尽可能高效率的算法,输入一个已经按升序排序过的整数数组和一个整数数字,在数组中查找两个数,使得它们
输入一个按升序排序过的整数数组{1、2、4、7、11、15}以及一个整数数字15,可以从该数组中找到两个数字,即4和11,使得4+11=15。请实现一个时间上尽可能高效率的算法,输入一个已经按升序排序过的整数数组和一个整数数字,在数组中查找两个数,使得它们
admin
2014-04-17
32
问题
输入一个按升序排序过的整数数组{1、2、4、7、11、15}以及一个整数数字15,可以从该数组中找到两个数字,即4和11,使得4+11=15。请实现一个时间上尽可能高效率的算法,输入一个已经按升序排序过的整数数组和一个整数数字,在数组中查找两个数,使得它们的和正好是输入的那个整数数字。如果有多对数字的和等于输入的整数数字,输出任意一对即可。要求:
说明你所设计算法的时间复杂度。
选项
答案
时间复杂度分析:在while的循环中,每次根据curSum和sum之间的大小关系来决定是改变ahead还是改变behind。这个过程每次是O(1)的。在整个算法流程中,因为ahead始终大于behind,如果一个数被ahead扫过了,那么它不会被behind扫到,也不会被ahead再次扫到;同样的,如果一个数被behind扫过了,那么它将不会再被ahead或者behind扫到。所以循环最多执行n—1次就会结束,故整个算法的时间复杂度为O(n)。
解析
转载请注明原文地址:https://kaotiyun.com/show/iYxi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
清初设置的两个“办事大臣”是()。①宁古塔②西宁③库伦④西藏
在努力纠正“文化大革命”错误的过程中,遇到的严重障碍是()
古埃及中王国时期出现了一个新兴的手工业部门,对世界文明做出了巨大贡献。这一新兴的手工业部门是()。
在巴黎和会上获利最大的两个国家是()。
十六国时期的历史,可以划分为前后两个时期,其分界线是()。
“二战”后主要资本主义国家经济恢复和发展的杠杆是()。①政府采取宏观调控政策②发展国家垄断资本主义③充分利用科技成果④加强国际经济联系
某激光打印机每分钟打印20页,每页4000字符,相应的设备驱动程序一次输出一个字符,采用中断方式,CPU处理每次中断需50微秒,则CPU用于打印的开销是()。
下列描述中,属于冯.诺依曼体系结构的特点是()。①采用流水线技术;②指令和数据均以二进制表示;③存储程序并且存储时不区别数据和指令。
现有一个解决无向连通图的最小生成树的一种方法如下:将图中所有边按权重从大到小排序为(el,e2,…,em);i=1;while(所剩边数>=顶点数){从图中删去ei;若图不再连通。则恢复ei;i=
下图中的顶点表示村庄,有向边代表交通路线,若要建立一家医院,试问建在哪一个村庄能使各村庄总体交通代价最小?
随机试题
解放战争时期,中国共产党直接领导大区人民政府的机构是()
26岁,G1P1,31周妊娠,规律性腹痛3h入院。查体:宫底高度30cm,LOA,胎心120次/分,宫缩20s/5~7min。肛门检查:宫颈管消退70%,宫口尚未扩张。不宜选用的处理措施是()
雌、孕激素在哪些器官生理作用中相互拮抗()
A.>750m1B.<400mlC.<100mlD.<50mlE.>2500ml无尿指每日尿量
袋中共有5个球,其中3个新球,2个旧球,每次取1个,无放回的取2次,则第二次取到新球的概率是()。
生产安全事故调查处理的原则是()。
暴力慈善是一种慈善的暴力行为,以牺牲受赠人的尊严来获得自己的满足。暴力慈善是对高调行善行事方式的一种概括。根据上述定义,下列哪项中的现象不属于暴力慈善?
关于计算机网络分类的描述中,错误的是()。
下列有关类继承的表述中,错误的是
TheSkillsRequiredtoGetaJobI.Academicskills:【T1】______【T1】______1.Communicationskills—Understandandspeakthelang
最新回复
(
0
)