首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
输入一个按升序排序过的整数数组{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
87
问题
输入一个按升序排序过的整数数组{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
学硕统考专业
相关试题推荐
万历年间,()的获得使得佃农与地主之间只存在单纯的经济强制关系,没有人身依附关系
中华人民共和国恢复了在联合国合法席位的时间是()。
第二次工业革命引起的生产关系方面最突出的变化是()。
试析淝水之战前后南北政权的特点和变化。
根据下列史料,说明朝鲜社会性质发生了怎样的变化。第四款朝鲜釜山之草粱项设有日本公馆,久为两国人民通商之地。从今日起,改革从前惯例及岁遣船等事,以此次新订条款为标准,办理贸易事务,朝鲜政府开放第五款所载两口岸,准日本人民往来通商,随意在该两地租借地
印度种姓制度中,处于被剥削被压迫地位的两个瓦尔那是()①婆罗门②刹帝利③首陀罗④吠舍
我国古代文献中记载了许多有关部落和部落联盟之间发生大规模战争的传说,如炎帝和黄帝两个部落曾战于(),结果黄帝取得了胜利。
某计算机采用微程序控制方式,微指令字长32位,采用字段直接编码的控制方式,共有55个微命令,可分为6个互斥组,分别包含1、3、7、8、12、24个微命令。另外,该机共有5个可判定的外部条件,采用断定方式形成后续微指令地址。(1)设计该机微指令的格式,
指令字长为12位,每个地址码为3位,采用扩展操作码的方式,设计4条三地址指令、16条二地址指令、64条一地址指令和16条零地址指令。(1)给出一种操作码的扩展方案。(2)计算该方案操作码的平均长度。
随机试题
关于“表”与“里”的相对概念,正确的有
钢筋混凝土简支矩形截面梁尺寸为250mm×500mm,混凝土强度等级为C30,梁受拉区配置3φ20的钢筋(942mm2),混凝土保护层c=25mm,承受均布荷载,梁的计算跨度I0=6m。已知按荷载效应的准永久组合计算的跨中弯矩值Mq=90kN.m,受拉
关于冯.诺依曼原理,以下叙述错误的是()。
Mary’sfriendsarelookingforwardwithhope()fromher.
学习者持续一贯的带有个性特征的学习方式是()。
自我评价能力是进行自我教育认识的基础。()
在中国人民革命即将取得全国胜利的前夕,中国共产党在河北省平山县西柏坡村召开了七届二中全会,其主要内容有()
ThemostimportantresultoftheLewisandClarkexpeditionwasthatitenabledtheUnitedStatestoclaimtheOregonregion.
Fool______Jerryis,hewouldnothavedonesuchathing.(2010年考试真题)
证明信说明:假设你是公司的经理张青,为李韵提供一份工作证明。内容:1.李韵从2008年6月至2010年7月在本公司担任秘书工作;2.任职期间十分负责任,努力勤奋,善于团队合作;3.公司对她的表现十分满意。
最新回复
(
0
)