首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
输入一个按升序排序过的整数数组{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-11-20
95
问题
输入一个按升序排序过的整数数组{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/9VRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
中国第一个资产阶级革命团体兴中会建立的时间是()。
万历年间,()的获得使得佃农与地主之间只存在单纯的经济强制关系,没有人身依附关系
1994年5月,江泽民在进一步强调正确处理改革、发展、稳定的关系时指出()。
康有为在他的《孔子改制考》中将孔子奉为主张变革的先驱,下列描述正确的是()
在巴黎和会上获利最大的两个国家是()。
北约和华约两个组织对峙近半个世纪,其影响是()。
根据下列史料,说明朝鲜社会性质发生了怎样的变化。第四款朝鲜釜山之草粱项设有日本公馆,久为两国人民通商之地。从今日起,改革从前惯例及岁遣船等事,以此次新订条款为标准,办理贸易事务,朝鲜政府开放第五款所载两口岸,准日本人民往来通商,随意在该两地租借地
我国古代文献中记载了许多有关部落和部落联盟之间发生大规模战争的传说,如炎帝和黄帝两个部落曾战于(),结果黄帝取得了胜利。
指令系统字长16位,每个地址码为6位,采用扩展操作码的方式,试设计14条二地址指令,100条一地址指令,100条零地址指令。(1)画出操作码的扩展形式。(2)下图为指令译码逻辑图,其中只给出了二地址指令的译码逻辑,试补全一地址指令和零地址指令的
随机试题
大宗货物租船订舱的提出办理时间一般应为()。
男性,45岁,间断腹痛、腹泻3年,排便4~5次/天,便不成形,无脓血、黏液,服黄连素、氟哌酸可稍缓解,近半月症状加重,大便7~8次/日,查大便常规正常。治疗哪种方法最适当
在引起产褥感染的病原体中临床最常见的是
A.检查者偏倚B.回忆偏倚C.报告偏倚D.选择性偏倚E.无应答偏倚由于某些原因受检者未接受检查而造成的偏倚是
幽门梗阻病人长期呕吐可引起的水电解质酸碱失衡的类型是()
宪法的基本特征是()
下列属于高填方路基沉降病害防治措施的是( )。
阅读下面这首诗歌,完成试题。清溪行①李白清溪清我心,水色异诸水。借问新安江②,见底何如此?人行明镜中,鸟度屏风里。向晚猩猩啼,空悲远游子。【注】①清溪
把“三个代表”重要思想确立为党的指导思想并写进党章的会议是()。
西太平洋是全球海山系统分布最为集中的海域,人类对此处海山的认识却非常有限。西太平洋的马里亚纳海沟是板块俯冲地带,海底地质运动非常活跃,海山火山岩的物质组成及成因等是海洋地质科学家感兴趣的问题;西太平洋的暖池和北赤道流等对中国气候有重要影响,是物理海洋科学家
最新回复
(
0
)