首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
输入一个按升序排序过的整数数组{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
36
问题
输入一个按升序排序过的整数数组{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
学硕统考专业
相关试题推荐
()是解放战争时期西北战场的关键一次战役,是西北战局的转折点。
标志着南京国民政府在全国范围内形式上完成统一的事件是()。
1978年直接领导和发动真理标准问题讨论的中央领导人是()。
结合学界已有成果,评析李鸿章晚清外交活动。(北京大学2013年中国史真题)
论述斯巴达的阶级结构、政治制度和社会风尚
1946年5月,中共中央发布的实现“耕者有其田”政策的重要文件是()。
阅读材料,回答问题:材料一:巴尔干半岛和东地中海地区,历来被英国视为大英帝国的生命线。大战结束前后,美国利用种种借口,千方百计渗入这个连接欧亚两大洲的重要战略地区……1947年2月21日,英国向美国国务院发出了结束援助希腊、土耳其的照会,声称国内严重的经
“二战”后主要资本主义国家经济恢复和发展的杠杆是()。①政府采取宏观调控政策②发展国家垄断资本主义③充分利用科技成果④加强国际经济联系
随机试题
什么是静息电位?简述其产生机制。
Thefirsttruepieceofsportsequipmentthatmaninventedwastheball.InancientEgypt,aseverywhere,pitchingstoneswa
治疗劳伤心脾之遗精可选的方剂是
A.腹股沟斜疝B.交通性鞘膜积液C.两者均是D.两者均不是(1993年)站立位阴囊出现包块,平卧位消失者,是
()是一种不主要依赖发起人的信贷或涉及的有形资产,而主要是以项目本身的效益和项目的资产与现金流量为支持的融资方式。
下面财政手段中,属于“内在稳定器”的是( )。
企业采用公允价值模式核算投资性房地产的,对于新取得的公允价值无法可靠计量的投资性房地产,可以采用成本模式计量。()
甲公司拟建造一幢厂房,2007年1月1日向银行专门借款1000万元,期限为3年,年利率为12%,每年1月1日付息。2007年度甲公司使用专门借款800万元用于厂房的建设,余款存于银行,银行年未存款结息11.25万元。则甲公司2007年度借款费用应予资本化
如果某测验的信度系数为0.80,那么该测验中真分数造成的变异占()。
《英国医学杂志》发表的一篇研究成果显示:吃白米饭最多的人和最少的人比,患糖尿病的风险会增加55%。有人据此得出结论,多吃白米饭易患糖尿病。以下哪项如果为真,最能削弱上述结论?()
最新回复
(
0
)