首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
输入一个按升序排序过的整数数组{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-11-20
24
问题
输入一个按升序排序过的整数数组{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://jikaoti.com/ti/HLfjFFFM
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
【波兹南事件】北京大学2003年欧美近现代史真题;华中师范大学2015年世界史基础真题
1917年发生的开辟人类历史新纪元的重大事件是()。
明朝初加强专制统治的措施中,与后来宦官专权有直接关系的是()。
康有为在他的《孔子改制考》中将孔子奉为主张变革的先驱,下列描述正确的是()
在巴黎和会上获利最大的两个国家是()。
洪武年间修复过的水利工程有()。
解放军渡江战役中横渡长江的东西两个攻击点是()。
我国古代文献中记载了许多有关部落和部落联盟之间发生大规模战争的传说,如炎帝和黄帝两个部落曾战于(),结果黄帝取得了胜利。
有两部计算机M1和M2,指令系统相同。它们的操作频率频率分别是400MHz和200MHz。指令分成A、B和C三类,在M1上执行分别需4、6和8个周期;在M2上执行分别需2、4和3个周期。现有一程序在两机器上执行,其中A、B和C三类指令依次占30%、50
指令字长为12位,每个地址码为3位,采用扩展操作码的方式,设计4条三地址指令、16条二地址指令、64条一地址指令和16条零地址指令。(1)给出一种操作码的扩展方案。(2)计算该方案操作码的平均长度。
随机试题
电脑:设备
Yesterdaywesawa______filmabouttheIndependenceWar.
A.正中神经受卡压B.尺神经受卡压C.桡神经受卡压D.坐骨神经受卡压肘管综合征是指
注册会计师对被审单位财务报告的最好评价是无保留意见。()
甲乙双方签订一份保管合同,合同规定,甲代乙保管货物100吨,价值300万元,凡是保管期间货物发生损失的,由甲赔偿损失,保管期间1年,保管费22万元,则双方就该保管合同需要缴纳的印花税为( )元。
复利期间数量是投资期内复利的次数。()
有一个抢劫犯。由于证据不足,很难做起诉决定.但如果不起诉。又会引起极大的民愤。作为公诉人你怎么办?
16,81,256,625,()。
某公司今年公开招聘时,平均每个职位的应聘人数比去年减少了10%。因此,该公司对求职者的吸引力有所降低。以下最能削弱上述推论的一项是()。
Shewas,______herfameandfortune,basicallyanunhappywoman.
最新回复
(
0
)