首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
输入一个按升序排序过的整数数组{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
28
问题
输入一个按升序排序过的整数数组{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
学硕统考专业
相关试题推荐
中国第一个资产阶级革命团体兴中会建立的时间是()。
二战后期,反法西斯同盟国召开了一系列会议、达成了一系列协议,以解决战后世界的安排问题,这些会议中以()最为重要,所以,我们将二战后的国际关系格局称为()。
晚清时期清帝年号的正确排序是()
在巴黎和会上获利最大的两个国家是()。
根据下列史料,说明朝鲜社会性质发生了怎样的变化。第四款朝鲜釜山之草粱项设有日本公馆,久为两国人民通商之地。从今日起,改革从前惯例及岁遣船等事,以此次新订条款为标准,办理贸易事务,朝鲜政府开放第五款所载两口岸,准日本人民往来通商,随意在该两地租借地
晚清时期清帝年号的正确排序是
1854年,英国外交大臣致函英国驻华公使说:“为了适应外商对农业产品已增加了的需要,新的贸易市场尚待开辟。”1856年,法国外长则指令法国驻华代办强调“商业关系的推广”,并强调“这是一个关系到至高无上权益的问题”。这说明()。
某机字长32位,采用定长操作码,单字长指令,共有机器指令100条,CPU内部有通用寄存器32个,可作变址寄存器用,存储器按字节编址,指令拟用直接寻址、间接寻址、变址寻址和相对寻址等4种寻址方式。(1)分别画出寻址方式由操作码指出和寻址方式由专用字
随机试题
Duringherjunioryearofhighschool,CandiceBackus’steacherhandedherasheetandinstructedthe17-year-oldtomapouther
维持蛋白质二级结构的主要化学键是
A、阻断M-胆碱受体B、阻断黑质纹状体多巴胺受体C、阻断中脑边缘叶和中脑皮质通路中多巴胺受体D、阻断α-肾上腺素受体E、阻断结节漏斗通路中多巴胺受体氯丙嗪引起口干、便秘、视力模糊是由于
下列选项属于建设工程投资特点的有( )。
以下市场细分行为中,违反可衡量性原则的是()。(2012年上半年)
下列各项做法中,可以应对舞弊导致的重大错报风险的有()。
公文中的密级分为()三个等级。
依次填入下列各句横线处的词语,最恰当的一组是()①报载孙中山的孙女孙穗芳女士近年多次______北京大学,为推动孙中山研究做出了贡献。②北京市政府对城市建设布局做出了______,在2008年前将每年增加800万平米的绿地。③
《西厢记》全名《崔莺莺待月西厢记》共五本二十一折,写的是书生张生和前相国女儿崔莺莺的爱情故事,故事的主要情节来源于唐代______的传奇《莺莺传》(又名《会真记》)。
防火墙主要可以分为______、代理服务器和应用级网关等类型。
最新回复
(
0
)