首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
输入一个按升序排序过的整数数组{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
2014-04-17
33
问题
输入一个按升序排序过的整数数组{1、2、4、7、11、15}以及一个整数数字15,可以从该数组中找到两个数字,即4和11,使得4+11=15。请实现一个时间上尽可能高效率的算法,输入一个已经按升序排序过的整数数组和一个整数数字,在数组中查找两个数,使得它们的和正好是输入的那个整数数字。如果有多对数字的和等于输入的整数数字,输出任意一对即可。要求:
给出算法的基本设计思想。
选项
答案
基本设计思想:如果不考虑时间复杂度,最简单的想法是先在数组中固定一个数字,再依次判断数组中剩下的n—1个数字与它的和是不是等于输入的数字。可惜这种思路需要的时间复杂度是O(n
2
),不满足题意要求。 假设现在随便在数组中找到两个数,如果它们的和等于输入的数字,则找到了要找的两个数字;如果小于输入的数字呢,则希望两个数字的和再大一点。当两个数字的和大于输入的数字的时候,把较大的数字往前移动,因为排在数组前面的数字要小一些,它们的和就有可能等于输入的数字了。 把前面的思路整理一下:找到数组的第一个数字和最后一个数字。当两个数字的和大于输入的数字时,把较大的数字往前移动;当两个数字的和小于数字时,把较小的数字往后移动;当相等时,正合题意。
解析
转载请注明原文地址:https://kaotiyun.com/show/4Yxi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
简述近代香港问题的形成。
西藏自治区的设立时间是()。
八路军建立的第一个敌后抗日民主根据地是()。
从鸦片战争的过程和结局可以看出,()是决定战争胜败的关键。
北魏建立和统一的时间分别是()。
下列对凡尔赛和约中有关德国疆界问题的表述,正确是()。
二战后主要资本主义国家经济恢复和发展的杠杆是()①政府采取宏观调控政策②发展国家垄断资本主义③充分利用科技成果④加强国际经济联系
二战后期,反法西斯同盟国召开了一系列会议、达成了一系列协议,以解决战后世界的安排问题,这些会议中以()最为重要,所以,我们将二战后的国际关系格局称为()。
与前两次工业革命相比,第三次科技革命在能源结构上的主要变化是()
把中国第一次工人运动的高潮推向顶点的是()。
随机试题
公安政策是由全国人民代表大会提出来的,体现了全国人民的意志。()
远期汇率与即期汇率之间存在差额,当差额用贴水表示时,说明远期汇率__________即期汇率。()
战略重点
与抗胃壁细胞抗体有关的疾病是
SD-SK自下述哪一种细菌
在建设工程中由于指定分包商违约或延误造成的索赔,属于承包商向业主索赔原因中的()。
佛教四大圣地中,佛的成道地是()。
对出版专门以未成年人为对象的()等出版物,国家给予扶持。(2014.湖南)
能否把组织中已建立并正在使用的数据库直接,为新开发的决策支持系统所用?
HowaretheguestsgoingtoNewYork?
最新回复
(
0
)