首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
输入一个按升序排序过的整数数组{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
19
问题
输入一个按升序排序过的整数数组{1、2、4、7、11、15}以及一个整数数字15,我们可以从该数组中找到两个数字,即4和11,使得4+11=15。请实现一个时间上尽可能高效率的算法,当输入一个已经按升序排序过的整数数组和一个整数数字,在数组中查找两个数,使得它们的和正好是输入的那个整数数字。如果有多对数字的和等于输入的整数数字,输出任意一对即可。要求:
给出算法的基本设计思想。
选项
答案
基本设计思想:如果我们不考虑时间复杂度,最简单的想法是先在数组中固定一个数字,再依次判断数组中剩下的n-1个数字与它的和是不是等于输入的数字。可惜这种思路需要的时间复杂度是O(n
2
),不满足题意要求。 假设现在随便在数组中找到两个数,如果它们的和等于输入的数字,那太好了,我们找到了要找的两个数字;如果小于输入的数字呢?我们希望两个数字的和再大一点。由于数组已经排好序了,我们是不是可以把较小的数字往后面移动一个数字?因为排在后面的数字要大一些,那么两个数字的和也要大一些,就有可能等于输入的数字了;同样,当两个数字的和大于输入的数字的时候,我们把较大的数字往前移动,因为排在数组前面的数字要小一些,它们的和就有可能等于输入的数字了。 我们把前面的思路整理一下:最初我们找到数组的第一个数字和最后一个数字。当两个数字的和大于输入的数字时,把较大的数字往前移动;当两个数字的和小于数字时,把较小的数字往后移动;当相等时,正合题意。
解析
转载请注明原文地址:https://kaotiyun.com/show/1VRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
【波兹南事件】北京大学2003年欧美近现代史真题;华中师范大学2015年世界史基础真题
在下列我国建国之后的外交活动中,能够体现“和而不同”思想的有()①亚非会议主张“求同存异”②提出“和平共处五项原则”③中日关系实现正常化④同第三世界国家建立友谊
二战后期,反法西斯同盟国召开了一系列会议、达成了一系列协议,以解决战后世界的安排问题,这些会议中以()最为重要,所以,我们将二战后的国际关系格局称为()。
毛泽东认为,社会主义这个阶段可分为两个阶段,包括()。
晚清时期清帝年号的正确排序是()
西汉初年,西域共有36国,其中以()人口最多。
解放军渡江战役中横渡长江的东西两个攻击点是()。
第二次工业革命引起的生产关系方面最突出的变化是()。
某计算机采用微程序控制方式,微指令字长32位,采用字段直接编码的控制方式,共有55个微命令,可分为6个互斥组,分别包含1、3、7、8、12、24个微命令。另外,该机共有5个可判定的外部条件,采用断定方式形成后续微指令地址。(1)设计该机微指令的格式,
随机试题
《民政部关于进一步加快推进民办社会工作服务机构发展的意见》针对加强民办社会工作服务机构能力建设提出了()要求。
计算
A.吸宫不全B.子宫复旧不良C.宫外孕D.子宫穿孔E.宫颈裂伤
下列说法不正确的有哪些?
某建筑公司承包了一项混凝土框架结构大型商场工程的施工。其依法可以将( )工程分包给具有相应施工资质的其他建筑企业。
( )发生的债权,债务人不履行债务的,债权人有留置权。
以下属于信息传递程序控制的内容有()。
下列项目中,计征企业所得税时不允许扣除的项目有( )。
某企业的投资性房地产采用成本模式计量,投资性房地产业务不属于企业的主营业务,按期计提折旧或进行摊销时应该借记的科目是()。
A、 B、 C、 A
最新回复
(
0
)