首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
输入一个按升序排序过的整数数组{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
75
问题
输入一个按升序排序过的整数数组{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年世界史基础真题
在下列我国建国之后的外交活动中,能够体现“和而不同”思想的有()①亚非会议主张“求同存异”②提出“和平共处五项原则”③中日关系实现正常化④同第三世界国家建立友谊
下列事件最能体现对苏联民主制造成重大破坏的是()。
明朝初加强专制统治的措施中,与后来宦官专权有直接关系的是()。
十六国时期的历史,可以划分为前后两个时期,其分界线是()。
毛泽东认为,社会主义这个阶段可分为两个阶段,包括()。
第二次世界大战后,国际关系最大的变化是()。
北约和华约两个组织对峙近半个世纪,其影响是()。
指令系统字长16位,每个地址码为6位,采用扩展操作码的方式,试设计14条二地址指令,100条一地址指令,100条零地址指令。(1)画出操作码的扩展形式。(2)下图为指令译码逻辑图,其中只给出了二地址指令的译码逻辑,试补全一地址指令和零地址指令的
在请求分页存储管理中,若采用FIFO的页面淘汰算法,当分配的页面数增加时,缺页中断的次数()。
随机试题
在这种路口遇到行人突然横穿怎么办?
张某系某县人民政府卫生局的一名副科长。2003年3月,张某因在街头与人争吵,失手将他人打伤,因而受到行政拘留处罚。县卫生局非常重视此事,鉴于其行为造成恶劣的社会影响,除对张某进行严肃批评教育外,并依照法定程序给予张某撤销副科长职务的行政处分。张某对此没有异
肝气上逆的临床表现有
女性,35岁,颈前区肿块10年,近年来易出汗、心悸,渐感呼吸困难。体检:晨起心率104/分,BPl20/60mmHg;无突眼,甲状腺Ⅲ度肿大,结节状,心电图示:窦性心律不齐。最佳的治疗方法是
下列霍乱休克抢救中哪项措施是错误的
影响药物制剂稳定性的处方因素不包括()
下列偏差分析方法的优点中,表格法所没有的是()。
北伐战争中在湖北和湖南战场上消灭的是()的主力。
汉代积极地经营西域地区,在河西走廊设有四郡,其中不包括()
若a,b都是质数,且a2+b=2003,则a+b的值等于().
最新回复
(
0
)