首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
输入一个按升序排序过的整数数组{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-04-28
33
问题
输入一个按升序排序过的整数数组{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://kaotiyun.com/show/dWRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
()是一部上起传说中的黄帝,下迄汉武帝时期的中国通史,是中国历史上第一部内容完整、结构周密的历史著作。
在下列我国建国之后的外交活动中,能够体现“和而不同”思想的有()①亚非会议主张“求同存异”②提出“和平共处五项原则”③中日关系实现正常化④同第三世界国家建立友谊
下列国家中,最早同新中国建立外交关系的是()
关于德意志宗教改革的说法不正确的是()
在欧盟发展历史上,促使欧盟正式成立的文件是()。
1543年,发表了解剖学专著《人体结构》的是()。
阅读下面史料,回答问题:材料一各缔约国主力舰替换总吨位按照标准排水量计算不得超过如下:合众国525000吨;英帝国525000吨;法国175000吨;意大利175000吨;日本315000吨。
一个字节多路通道连接D1、D2、D3、D4、D5共5台设备,这些设备分别每10μs、30μs、30μs、50μs和75μs向通道发出一次数据传送的服务请求,请回答下列问题:(1)计算这个字节多路通道的实际流量和工作周期。(2)如果设计字
在下列事件中,哪个不是设备分配中应该考虑的问题()。
在一个8级中断的系统中,硬件中断响应从高到低的优先顺序是1→2→3→4→5→6→7→8,通过中断屏蔽技术,将中断处理优先顺序设置为1→3→5→7→2→4→6→8,如果CPU在执行一个应用程序时有5、6、7、8级的四个中断同时到达,CPU在按优先顺序处理到第
随机试题
有关孕激素的作用,下列叙述错误的是
Theway_____helooksatproblemsiswrong.
肱三头肌反射的反射中枢在
陶瓷制输变电线路绝缘套管()
简述义务教育阶段语文课程的总体目标与内容。
Atdusk,Mr.Hightowerwouldsitinhisoldarmchairinthebackyardandwistfullyloseinreminiscenceofhisyouthromances.
下表为同时开展的4个项目在某个时刻的计划值(PV)、实际成本(AV)和挣值(EV),该时刻成本超出最多的项目和进度最为落后的项目分别是(57)。
用户A从CA获得用户B的数字证书,并利用______验证数字证书的真实性。
关系数据库的规范化理论指出:关系数据库中的关系应满足一定的要求,最起码的要求是达到1NF,即满足()。
(1)Mostpeopledreamenthusiasticallyatnight,theirdreamsseeminglyoccupyinghours,eventhoughmostlastonlyafewminutes
最新回复
(
0
)