首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
输入一个按升序排序过的整数数组{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
32
问题
输入一个按升序排序过的整数数组{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
学硕统考专业
相关试题推荐
水门事件
洪武年间修复过的水利工程有()。
十六国时期的历史,可以划分为前后两个时期,其分界线是()。
下列现象均属于明朝手工业进步的表现的是()①嘉万年间民营手工业渐居主要地位②匠役制度瓦解③出现了雇佣劳动、组织手工工场的经营方式④加强了对工匠的剥削,工匠的人身依附关系加强
与前两次工业革命相比,第三次科技革命在能源结构上的主要变化是()
北约和华约两个组织对峙近半个世纪,其影响是()。
试析淝水之战前后南北政权的特点和变化。
某计算机采用微程序控制方式,微指令字长32位,采用字段直接编码的控制方式,共有55个微命令,可分为6个互斥组,分别包含1、3、7、8、12、24个微命令。另外,该机共有5个可判定的外部条件,采用断定方式形成后续微指令地址。(1)设计该机微指令的格式,
关于分页系统,回答下列问题:(1)在页表中,哪些数据项是为实现换页而设置的?(2)设某系统为每个作业进程分配3个内存块,某作业进程在运行访问中的轨迹为1,4,3,1,6,8,1,且每一页都是按请求装入的。问:先进先出页面置换算法(FIF
指令字长为12位,每个地址码为3位,采用扩展操作码的方式,设计4条三地址指令、16条二地址指令、64条一地址指令和16条零地址指令。(1)给出一种操作码的扩展方案。(2)计算该方案操作码的平均长度。
随机试题
某市人民法院受理了该市人民检察院提起公诉的被告人张某盗窃案,在庭前审查阶段,下列哪些事项不属于审查的内容?
简述斑蝥的功效及主治证。
嗜温菌的生长温度为
有关停止吸氧的操作,下列正确的叙述是
国学是相对于“西学”而言的。从逻辑上说,甚至是先有西学,然后才有国学之说。晚清以前,中国士人生活于自己构想的“天下”中,不知有“西学”,也就不会说“国学”。文明尽在中国,只有中国有学,何以分中、西?待到19世纪末,因为甲午战败,士大夫产生了文化危
2016年4月15日是首个全民国家安全教育日,习近平总书记再次强调国家安全是“头等大事”。通过成立一个机构、构建一个法律体系、讲清一个问题、抓牢一个落脚点,“头等大事”得到全面落实。下列有关说法错误的是()。
鸡尾酒会效应:在鸡尾酒会上.很多人在同时进行着各种交谈.但一个人同一个时刻只能注意和参与其中的一个交谈,这是注意分配的问题。由于心理资源有限,同一时刻只能将信息加以过滤和筛选,以此刻最重要或最有兴趣的信息为注意对象。作为一个选择过滤器,注意就像收音机上的旋
下列现象中,可以说明教育对社会发展起促进作用的是
已知汉字“家”的区位码是2850,则其国标码是()。
Educationofexceptionalchildrenmeansprovisionofspecialeducationalservicestothosechildrenwhoareeitherhandicappedo
最新回复
(
0
)