首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
输入一个按升序排序过的整数数组{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
64
问题
输入一个按升序排序过的整数数组{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/9VRi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
下列事件最能体现对苏联民主制造成重大破坏的是()。
明朝初加强专制统治的措施中,与后来宦官专权有直接关系的是()。
十六国时期的历史,可以划分为前后两个时期,其分界线是()。
晚清时期清帝年号的正确排序是()
中华人民共和国恢复了在联合国合法席位的时间是()。
与前两次工业革命相比,第三次科技革命在能源结构上的主要变化是()
解放军渡江战役中横渡长江的东西两个攻击点是()。
1973年,以美元为中心的资本主义世界货币体系崩溃,反映出()。①国际金融领域内美元地位衰落②美国由债权国变为债务国③资本主义国家实力的对比发生了新的变化④美国的世界经济地位严重动摇
1984年,《中共中央关于经济体制改革的决定》中强调,商品经济的充分发展是社会经济发展不可逾越的阶段,市场调节的辅助性作用不可缺少,并指出要有步骤地逐步缩小指令性计划的范围。这表明当时我国()
1854年,英国外交大臣致函英国驻华公使说:“为了适应外商对农业产品已增加了的需要,新的贸易市场尚待开辟。”1856年,法国外长则指令法国驻华代办强调“商业关系的推广”,并强调“这是一个关系到至高无上权益的问题”。这说明()。
随机试题
不属于氯丙嗪作用的是
金属包装材料中产量和消耗量最多的是()
()是投资可能出现的最坏的情况,也是投资者可能需要承担的损失。
通常情况下,新员工和组织相互发现通常发生在()。
越来越多的人意识到遵守交通规则的重要性。
尊敬的宋楚瑜主席,尊敬的各位来宾,各位朋友:时维九月,序属三秋,我们相聚在美丽的黄浦江畔,隆重举办第一届两岸民间精英论坛。我们高兴地看到,一大批海峡两岸的知名专家学者、企业家应邀与会,共同探讨两岸经济交流与合作,共同筹划两岸关系发展的未来。此时此地,群贤毕
世界上最长的运河京杭大运河沟通了()大水系。
世界上最坚强的动物是什么?最近,欧洲空间局的研究人员宣布,他们利用无人太空舱所获得的航天实验数据显示,世界上最坚强的动物是一种我们肉眼看不清楚的水熊虫。这种小虫子能在太空的真空、超低温和强太阳辐射等多重极端恶劣环境条件下生存10天之久!2007年
本题为选做题,请在Ⅰ、Ⅱ两道试题中选取其中一道作答,若两题都回答,只按第Ⅰ道试题的成绩计入总分。选做题Ⅰ:以下是关于发展中国特色社会主义的相关材料:材料1改革开放以来我们取得一切成绩和进步的根本原因:开辟了中国特色社会主义道路,形成了中国特色社会主
主题数据库的概念和设计思想源于
最新回复
(
0
)