输入一个按升序排序过的整数数组{1、2、4、7、11、15}以及一个整数数字15，可以从该数组中找到两个数字，即4和11，使得4+11=15。请实现一个时间上尽可能高效率的算法，输入一个已经按升序排序过的整数数组和一个整数数字，在数组中查找两个数，使得它们

admin2014-04-17 52

问题输入一个按升序排序过的整数数组{1、2、4、7、11、15}以及一个整数数字15，可以从该数组中找到两个数字，即4和11，使得4+11=15。请实现一个时间上尽可能高效率的算法，输入一个已经按升序排序过的整数数组和一个整数数字，在数组中查找两个数，使得它们的和正好是输入的那个整数数字。如果有多对数字的和等于输入的整数数字，输出任意一对即可。要求：
说明你所设计算法的时间复杂度。

选项

答案时间复杂度分析：在while的循环中，每次根据curSum和sum之间的大小关系来决定是改变ahead还是改变behind。这个过程每次是O(1)的。在整个算法流程中，因为ahead始终大于behind，如果一个数被ahead扫过了，那么它不会被behind扫到，也不会被ahead再次扫到；同样的，如果一个数被behind扫过了，那么它将不会再被ahead或者behind扫到。所以循环最多执行n—1次就会结束，故整个算法的时间复杂度为O(n)。

解析

转载请注明原文地址:https://www.kaotiyun.com/show/iYxi777K

本试题收录于：计算机408题库学硕统考专业分类

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

计算机408

学硕统考专业

鸦片战争后中国社会思想领域发上了哪些重要变化。

“时方镇缺守帅，稍命文臣权之……又置转运使、通判，为之条禁，文薄渐为精密，由是利归公上而外权削矣。”这段文字反映出北宋初期加强地方控制的基本理念是()。

二战后期，反法西斯同盟国召开了一系列会议、达成了一系列协议，以解决战后世界的安排问题，这些会议中以()最为重要，所以，我们将二战后的国际关系格局称为()。

隋朝大运河中哪一段河道的地理位置最接近于春秋时期即已开通过的运河()?

某激光打印机每分钟打印20页，每页4000字符，相应的设备驱动程序一次输出一个字符，采用中断方式，CPU处理每次中断需50微秒，则CPU用于打印的开销是()。

某系统中n个相互独立的生产者进程为一个消费者进程提供数据，假设每个生产者提供的数据写入各不相同的缓冲区，且生产者写缓冲区的速度比消费者读缓冲区的速度快，则缓冲区个数的最优值应为()。

下列关于图的叙述中，正确的是____。I．回路是简单路径Ⅱ．存储稀疏图，用邻接矩阵比邻接表更省空间Ⅲ．若有向图中存在拓扑序列，则该图不存在回路

测量误差就其性质而言，可分为()。

掺入适量的缓凝剂能使混凝土()。

防火阀是在一定时间内能满足耐火稳定性和耐火完整性要求，用于管道内阻火的活动式封闭装置，下列应设置防火阀的部位有()。

某企业出售闲置的设备，账面原价21000元，已经使用两年，已经提折旧2100元，出售的时候发生清理费用400元，出售价格18000元，该企业出售此设备发生的净损益为()

2005年9月21日起，我国对活期存款实行按季度结息，每季度末月的()为结息日。

引起潮起潮落的主要因素是海风。()

战争文化研究运用了多种学科、多种理论和多种研究方法来解释战争与社会文化之问的互动关系，远比运用单一学科解释要得多，可以修正过去一些错误或存在的观点，也可以对历史进行另外一种角度的解释或观察。

YouwillhearoneoftheongoingseriesofinterviewswithaninfluentialexecutiveintheembeddedLinuxindustry—JimReady.

Aestheticsisthatregioninthelandofsciencewhosebordersofinvestigationareknownasexperiencesofbeauty,andwhoses

Whatyouhavesaidcannotbe______tomysmallfirm.

计算机408

学硕统考专业

鸦片战争后中国社会思想领域发上了哪些重要变化。

“时方镇缺守帅，稍命文臣权之……又置转运使、通判，为之条禁，文薄渐为精密，由是利归公上而外权削矣。”这段文字反映出北宋初期加强地方控制的基本理念是()。

二战后期，反法西斯同盟国召开了一系列会议、达成了一系列协议，以解决战后世界的安排问题，这些会议中以()最为重要，所以，我们将二战后的国际关系格局称为()。

隋朝大运河中哪一段河道的地理位置最接近于春秋时期即已开通过的运河()?

某激光打印机每分钟打印20页，每页4000字符，相应的设备驱动程序一次输出一个字符，采用中断方式，CPU处理每次中断需50微秒，则CPU用于打印的开销是()。

某系统中n个相互独立的生产者进程为一个消费者进程提供数据，假设每个生产者提供的数据写入各不相同的缓冲区，且生产者写缓冲区的速度比消费者读缓冲区的速度快，则缓冲区个数的最优值应为()。

下列关于图的叙述中，正确的是____。I．回路是简单路径Ⅱ．存储稀疏图，用邻接矩阵比邻接表更省空间Ⅲ．若有向图中存在拓扑序列，则该图不存在回路

测量误差就其性质而言，可分为()。

掺入适量的缓凝剂能使混凝土()。

防火阀是在一定时间内能满足耐火稳定性和耐火完整性要求，用于管道内阻火的活动式封闭装置，下列应设置防火阀的部位有()。

某企业出售闲置的设备，账面原价21000元，已经使用两年，已经提折旧2100元，出售的时候发生清理费用400元，出售价格18000元，该企业出售此设备发生的净损益为()

2005年9月21日起，我国对活期存款实行按季度结息，每季度末月的()为结息日。

引起潮起潮落的主要因素是海风。()

战争文化研究运用了多种学科、多种理论和多种研究方法来解释战争与社会文化之问的互动关系，远比运用单一学科解释要______得多，可以修正过去一些错误或存在______的观点，也可以对历史进行另外一种角度的解释或观察。

YouwillhearoneoftheongoingseriesofinterviewswithaninfluentialexecutiveintheembeddedLinuxindustry—JimReady.

Aestheticsisthatregioninthelandofsciencewhosebordersofinvestigationareknownasexperiencesofbeauty,andwhoses

Whatyouhavesaidcannotbe______tomysmallfirm.

战争文化研究运用了多种学科、多种理论和多种研究方法来解释战争与社会文化之问的互动关系，远比运用单一学科解释要得多，可以修正过去一些错误或存在的观点，也可以对历史进行另外一种角度的解释或观察。