首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
输入一个按升序排序过的整数数组{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
86
问题
输入一个按升序排序过的整数数组{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
学硕统考专业
相关试题推荐
【波兹南事件】北京大学2003年欧美近现代史真题;华中师范大学2015年世界史基础真题
下列事件最能体现对苏联民主制造成重大破坏的是()。
1994年5月,江泽民在进一步强调正确处理改革、发展、稳定的关系时指出()。
康有为在他的《孔子改制考》中将孔子奉为主张变革的先驱,下列描述正确的是()
毛泽东认为,社会主义这个阶段可分为两个阶段,包括()。
晚清时期清帝年号的正确排序是()
十六国时期的历史,可以划分为前后两个时期,其分界线是()。
北约和华约两个组织对峙近半个世纪,其影响是()。
以孙中山为首的革命派和以康有为代表的维新派,是推动近代中国社会变革的两个重要派别。两派主张的主要分歧在于()
指令字长为12位,每个地址码为3位,采用扩展操作码的方式,设计4条三地址指令、16条二地址指令、64条一地址指令和16条零地址指令。(1)给出一种操作码的扩展方案。(2)计算该方案操作码的平均长度。
随机试题
于老师上《感知与判断——美术鉴赏的过程与方法》一课前,要求学生收集他们自己认为美的作品的图片。此做法的意图是()。
TheunderlinedlettersinthefollowingwordshavethesamesoundEXCEPT_________.
Americansocietyisnotnap(午睡)friendly.Infact,saysDavidDinges,asleepspecialistattheUniversityofPennsylvaniaSchool
关于胸腺描述不正确的是
基准地价图上应表示出城镇中与土地区位和利用有关的主要道路,按《城镇土地估价规程》规定,市区内主干道在基准地价图上应该用()表示。
有会计科目编码如此定义,一级为4位,二级为3位,三级为2位,四级为2位,请问编码52101011009会计科目编码分级为()。
假设被评估企业所在的行业平均资金收益率为8%,净资产收益率为10%,而被评估企业预期年金收益为500万元,企业的股东全部权益价值(净资产现值)最有可能是( )万元。
下列加下划线的文字用括号内的词语替代后,不符合原意的一项是()。
宜居带是指一颗恒星周围一定距离的范围,在这一范围内水可以以液态形式存在。由于液态水被科学家认为是生命生存__________的元素,因此如果一颗行星恰好落在这一范围内,那么它就被认为有更大的__________拥有生命或至少拥有生命可以生存的环境。填入画
[A]library[B]bell[C]noon[D]visit[E]outside[F]camera[G]worrytomakeanoise
最新回复
(
0
)