首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
输入一个按升序排序过的整数数组{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
51
问题
输入一个按升序排序过的整数数组{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
学硕统考专业
相关试题推荐
水门事件
西汉初年,西域共有36国,其中以()人口最多。
战国时期的著名水利工程“郑国渠”位于今天的()。
1994年5月,江泽民在进一步强调正确处理改革、发展、稳定的关系时指出()。
解放军渡江战役中横渡长江的东西两个攻击点是()。
第二次工业革命引起的生产关系方面最突出的变化是()。
解放军渡江战役中横渡长江的东西两个攻击点是()。
指令系统字长16位,每个地址码为6位,采用扩展操作码的方式,试设计14条二地址指令,100条一地址指令,100条零地址指令。(1)画出操作码的扩展形式。(2)下图为指令译码逻辑图,其中只给出了二地址指令的译码逻辑,试补全一地址指令和零地址指令的
下图所示为双总线结构机器的数据通路,IR为指令寄存器,PC为程序计数器(具有自增功能),M为主存(受R/W信号控制),AR为地址寄存器,DR为数据缓冲寄存器,ALU由加、减控制信号决定完成何种操作,控制信号G控制的是一个门电路。另外,线上标注有小圈表示有控
指令字长为12位,每个地址码为3位,采用扩展操作码的方式,设计4条三地址指令、16条二地址指令、64条一地址指令和16条零地址指令。(1)给出一种操作码的扩展方案。(2)计算该方案操作码的平均长度。
随机试题
患者,男性,45岁。因腹主动脉瘤于某医院进行手术治疗,手术过程中突发大出血,经抢救无效死亡,根据《医疗事故处理条例》,以下行为被允许的是
中华民族精神的核心是
在Powerpoint2000中,幻灯片的配色方案可以通过______修改。
一个人失血达到多少时才可能会发生急性低血容量反应
口服胆系造影,在胆囊显影满意后服脂肪餐,多长时间再摄片观察胆囊收缩状况
“别克”轿车往复式活塞内燃发动机用的传动轴(排气量2000毫升)
下列各项中,应通过企业利润表中“营业成本”项目反映的有()。
一个随机抽取的顾客样本群体对一项市场调查中的问题做了回答。六个月后,另一个随机抽取的顾客样本群体回答了相同的问题,只是问题排列的顺序有所调整。两组样本对许多单个问题的回答方式有很大的差别,这表明有时只因排在前面的问题不同就会导致对后面问题的不同回答。上述论
设f(x,y)在全平面有三阶连续偏导数,并满足试求:
Readthistextabouteffectivebankingsupervision.Choosethebestsentencefromtheoppositepagetofilleachofthegaps
最新回复
(
0
)