首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
输入一个按升序排序过的整数数组{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
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://www.kaotiyun.com/show/iYxi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
鸦片战争后中国社会思想领域发上了哪些重要变化。
对三国鼎立到隋朝重新统一全国这段历史时期的政局,叙述正确的是()。①只有西晋有过短暂的统一②大多数时间是多个政权分立、南北对峙的复杂政局③西晋、北魏、东晋都有过短暂的统一④除三国分立以外,其他时间基本上处于统
下列不属于维也纳会议召开的目的的是()。
关于垄断组织的积极作用,不正确的说法是()。
重庆谈判的焦点问题是()
关于《新学伪经考》、《孔子改制考》的说法正确的是()。①都是利用古书古人宣传西方资产阶级政治的学说,向西方寻求救国真理②借用儒家学说和孔子的偶像进行宣传,可减少来自封建顽固势力的阻挠和压力③是维新变法的重要理论依据④动摇了封建统治的思想基
试编写一个非递归算法,实现求以二叉链表存储的二叉树中q结点的祖先。
将两个长度为N的有序表归并到一个长度为2N的有序表,最少需要比较的次数是(),最多需要比较的次数是()。
对于下图G,按下列条件试分别写出从顶点0出发按深度优先搜索遍历得到的顶点序列和按广度优先搜索遍历得到的顶点序列。(1)假定它们均采用邻接矩阵表示;(2)假定它们均采用邻接表表示,并且假定每个顶点邻接表中的结点是按顶点序号从大到小的次序链
已知有6个顶点(顶点编号为0~5)的有向带权图G,其邻接矩阵A为上三角矩阵,按行为主序(行优先)保存在如下的一维数组中。要求:画出有向带权图G。
随机试题
下列关于存储芯片与CPU连接时应注意的问题,说法错误的是()
设有χ-y平面上的直线运动路径,源点坐标为(1,1),终点坐标为(4,19),两轴只有加速度限制,其中χ轴的加速度限制为±2,y轴的加速度限制为±3。利用三次多项式样条函数生成点位控制指令,为保证所有轴的加速度都不超过容许值,求协调运动的容许最短时间为多少
德尔菲法的特征包括【】
白女士,74岁。以“间断性腹胀1月余”之主诉入院。患者1个月前无明显诱因出现腹胀,既往有乙肝病史14年。诊断:肝硬化失代偿期;腹水(大量)。医嘱:长期服用螺内酯可引起的不良反应是()
关于水痘的治疗,下面哪项是错误的?()
施工单位新入场的工人,必须接受公司、项目(或工区、工程处、施工队)、班组的三级安全培训教育,经考核合格后,方能上岗。
在施工时用石灰罩墙面时,为避免收缩,其正确的调剂方法是掺入()。
项目实施的工作项编码(项目实施工作过程的编码)应覆盖项目实施的工作任务目录的全部内容,它包括( )。
以下关于劳动定员与劳动定额的表述,不正确的是()。
A、I’llstayathome.B、Agoodidea.C、No,Iwon’tgothere.A
最新回复
(
0
)