首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
输入一个按升序排序过的整数数组{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
29
问题
输入一个按升序排序过的整数数组{1、2、4、7、11、15}以及一个整数数字15,可以从该数组中找到两个数字,即4和11,使得4+11=15。请实现一个时间上尽可能高效率的算法,输入一个已经按升序排序过的整数数组和一个整数数字,在数组中查找两个数,使得它们的和正好是输入的那个整数数字。如果有多对数字的和等于输入的整数数字,输出任意一对即可。要求:
给出算法的基本设计思想。
选项
答案
基本设计思想:如果不考虑时间复杂度,最简单的想法是先在数组中固定一个数字,再依次判断数组中剩下的n—1个数字与它的和是不是等于输入的数字。可惜这种思路需要的时间复杂度是O(n
2
),不满足题意要求。 假设现在随便在数组中找到两个数,如果它们的和等于输入的数字,则找到了要找的两个数字;如果小于输入的数字呢,则希望两个数字的和再大一点。当两个数字的和大于输入的数字的时候,把较大的数字往前移动,因为排在数组前面的数字要小一些,它们的和就有可能等于输入的数字了。 把前面的思路整理一下:找到数组的第一个数字和最后一个数字。当两个数字的和大于输入的数字时,把较大的数字往前移动;当两个数字的和小于数字时,把较小的数字往后移动;当相等时,正合题意。
解析
转载请注明原文地址:https://jikaoti.com/ti/RpajFFFM
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
分析第二次工业革命的特点及历史影响。
下面条约没有涉及德国的赔款问题的是()。
为了加强对地方的控制,唐太宗根据山川形势,把全国划分成10个(),经常派官员监察地方官吏。
“文化大革命”发动的两个纲领性文件是()。
20世纪初,革命派与改良派论战的中心问题是()。
结合学界已有成果,评析李鸿章晚清外交活动。(北京大学2013年中国史真题)
古埃及中王国时期出现了一个新兴的手工业部门,对世界文明做出了巨大贡献。这一新兴的手工业部门是()。
(1)以太网采用了曼彻斯特编码,一个比特的数据需要两个信号来传输,那么为了达到100Mbps的数据传送速率,需要线路达到200Mbps的带宽。(2)以太网的最小帧长度是64字节,那么发送一个最小帧需要的时间T1=64×8/(100×106),
已知加权有向图G如下,回答下列问题:(1)画出该有向图G的邻接矩阵;(2)试利用Dijkstra算法求G中从顶点a到其他各顶点间的最短路径,并给出求解过程。
随机试题
(2010年10月)进行非正式合作的各方在进行努力时,通常遵循一些行事规则,林德布洛姆认为其中最主要和最普通的规则是_________。
二妙散的适应证是防己黄芪汤的适应证是
此时证属()如寒邪较甚,苔薄白,脉浮紧,病属刚痉,治宜()
A.氯喹B.甲硝唑C.乙胺嘧啶D.吡喹酮E.伯氨喹主要用于控制疟疾症状的药物是()。
为政府、金融机构和企业提供筹集资金的渠道是()的基本功能。
企业按期计提车船税时,下列分录正确的是()。
—位教师在讲“摩擦力”一节时,一开始就提出:“把一个一吨重的铁球放在地面上,一只蚂蚁能不能推动它?”在学生响应后,接着问:“如果地面非常光滑呢?”这位教师在教学中运用的原则是()。
要坚持党的领导,必须不断改善党的领导。当前改善党的领导,应着力解决的问题有
Whilewe’veknownforsometimeaboutthemanylong-termbenefitsofexercise,newresearchshowsaerobicexercisealsomayhave
管理信息系统的概念结构是指管理信息系统是各职能子系统的一个联合体。每个子系统包含执行控制、【】及战略计划等三个信息处理部分。
最新回复
(
0
)