首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
输入一个按升序排序过的整数数组{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
19
问题
输入一个按升序排序过的整数数组{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/iYxi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
概述人民公社运动发生的原因、错误、危害及主要教训。
我国古代文献中记载了许多有关部落和部落联盟之间发生大规模战争的传说,如炎帝和黄帝两个部落曾战于(),结果黄帝取得了胜利。
简述清代秘密立储制的操作并作出评价。
晚清时期清帝年号的正确排序是()
十六国时期的历史,可以划分为前后两个时期,其分界线是()。
与前两次工业革命相比,第三次科技革命在能源结构上的主要变化是()
阅读材料,回答问题:材料一:巴尔干半岛和东地中海地区,历来被英国视为大英帝国的生命线。大战结束前后,美国利用种种借口,千方百计渗入这个连接欧亚两大洲的重要战略地区……1947年2月21日,英国向美国国务院发出了结束援助希腊、土耳其的照会,声称国内严重的经
某32位计算机系统采用段页式虚拟存储管理,现有一个进程被分成5段,其段号和段长见下表,段内分页,页表见下,存放在内存中,每页的长度为4096B。进程运行到某一个指令,其地址为(2,3,010),当前CPU的寄存器和地址加法器的状态如图所示,当上述指令执行时
随机试题
注册商标专用权所有人可以是()()()()。
现有前后两段落且段落格式也不同,当删除前一个段落标记时下列哪项正确()
A.眼睑不能闭合B.上睑下垂,眼球向上、向下、向内运动障碍C.眼球向下、向外运动减弱D.眼球向外转动障碍E.视物模糊动眼神经损害
脑复苏中首选的脱水剂为
噪声预测范围一般应()噪声评价等级所规定的范围。
【背景资料】某炼油厂管道安装为一个独立的单位工程,进行分部工程验收时,发现热力管道有几个钢制固定支架的主要受力构件尺寸小于设计尺寸,经原设计单位核算不能满足使用要求。【问题】分部工程验收时对质量检测有何要求?分部工程的质量等级应如何评定?
关于仲裁庭的说法,错误的是()。
D公司预期未来每年产生的永续现金流量在经济状况好的情况下为1500万元,经济状况不好的情况下只有500万元,预计经济状况好的可能性为60%,经济状况不好的可能性为40%。要求:假设企业处于完美资本市场中,如果企业借入了5000万元的债务,债务的期望报
TheUnitedStates【C1】______alargepartoftheNorthAmericancontinent.ItsneighborsareCanada【C2】______thenorth,【C3】______M
TherelationshipbetweenlanguagelearningstrategypreferencesandEnglishproficiencyamongstudentspuzzlesmanyEnglishlea
最新回复
(
0
)