首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
输入一个按升序排序过的整数数组{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
2017-04-28
27
问题
输入一个按升序排序过的整数数组{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/dWRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
()是一部上起传说中的黄帝,下迄汉武帝时期的中国通史,是中国历史上第一部内容完整、结构周密的历史著作。
二战后期,反法西斯同盟国召开了一系列会议、达成了一系列协议,以解决战后世界的安排问题,这些会议中以()最为重要,所以,我们将二战后的国际关系格局称为()。
下列不是苏俄实行战时共产主义政策原因的是()。
鸦片战争中,林则徐被革职查办反映的问题是()。
对巴黎公社的评述,正确的有()。①是无产阶级建立政权的第一次伟大尝试②主要的经验是废除旧的国家机器,建立新的国家机器③其实践和经验,丰富了马克思主义理论④由于无产阶级的不成熟,其失败是不可避免的
在周初分封中,分封同姓诸侯国、异姓诸侯国,也分封圣王之后,下面属于圣王之后的封国为()。
在一个8级中断的系统中,硬件中断响应从高到低的优先顺序是1→2→3→4→5→6→7→8,通过中断屏蔽技术,将中断处理优先顺序设置为1→3→5→7→2→4→6→8,如果CPU在执行一个应用程序时有5、6、7、8级的四个中断同时到达,CPU在按优先顺序处理到第
某系统有R1、R2和R3共3种资源,在TO时刻P1、P2、P3和P4这4个进程对资源的占用和需求情况如表4-4所示,此时系统的可用资源向量为(2,1,2)。试问:如果此时P1和P2均发出资源请求向量Request(1,0,1),为了保证系统的安全性,应
随机试题
任何飞机起降运行区除跑道外,还必须设置()。
Whatisthepurposeoftheannouncement?
WhichTWOofthefollowingpointsdoesthetutorwarnstudent’sresearchwork?AintervieweesBmakedataclearlyC
仁爱孝悌
可引起疟疾再燃的虫期为
张某为某医院内科医生,两年半之前到国外照顾子女,现回国希望继续到原医院工作。按规定,张医生应参加考核,并到县级以上卫生行政部门申请办理
风井如何计算建筑面积?[2010年第10题]
关于办公建筑采用的照明节能措施,错误的是()。
影响学前儿童亲社会行为的因素有哪些?请阐述之。
新课改倡导教师成为学生学习的促进者。()
最新回复
(
0
)