首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
输入一个按升序排序过的整数数组{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
27
问题
输入一个按升序排序过的整数数组{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/jpajFFFM
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
简要分析在蒸汽时代资本主义的决定性的胜利。
试析英法绥靖政策和美国中立政策的原因。(南京大学2013年国际关系史真题)
()后,辽东局势起了根本变化,明朝在军事上失去主动进攻的力量,而后金则由防御转入进攻。
下列内容,与垄断组织出现有关的是()。①控制一个或几个部门商品的生产、价格和市场②促进了大工业的发展,在某种程度上适应了生产力发展的需要③干预、控制国家的政治、经济生活④积极向外扩张,从经济上瓜分世界
与前两次工业革命相比,第三次科技革命在能源结构上的主要变化是()
十六国时期的历史,可以划分为前后两个时期,其分界线是()。
著名的绥靖政策文件《霍尔—赖伐尔协定》是英、法与意大利签订的,密谋发动()。
解放军渡江战役中横渡长江的东西两个攻击点是()。
阅读史料回答以下问题:天既哀大地生人之多艰,黑帝乃降精而救民患,为神明,为圣王,为万世作师,为万民作保,为大地教主。生于乱世,乃据乱世而立三世之法,而垂精太平。乃因其所生之国,而立三世之义,而注意于大地远近、大小若一之大一统。乃立元以统天,以天为
某32位机(机器字长32位)的一台外设通过32位总线与系统内存相连。CPU每秒执行100条指令,平均每条指令需要5个机器周期,其中3个周期必须访问内存,内存读写需一个机器周期,假定CPU在95%的时间内持续执行“背景程序”,且这段时间内不执行I/O指令。现
随机试题
允许外国公使进驻北京的条约是()
流行性出血热病毒是
油性软膏基质中加入羊毛脂的作用是( )。
某男甲与某女乙2000年登记结婚,婚后两人的感情非常冷淡,无法一起共同生活。2004年1月,乙以感情破裂为由向法院请求离婚,法院支持其主张的理由可以包括:
十进制数140转换为十六进制数为()。
按投资作用不同,工程建设项目可分为生产性建设项目和非生产性建设项目两大类。下列项目中属于非生产性建设项目的是( )。
据某市交警部门公布的数据,在该市全市上个月发生的13000多起汽车交通事故中,只有10%是因为司机酒后驾驶造成的。由此可见,酒后驾驶的危险性并不像某些交通宣传中所说的那么大。“酒后驾驶,等于送死”只是危言耸听的夸张宣传而已。假定以上数据无误,那么
2008年以来,索马里附近海域先后发生累计逾120起的海盗劫船事件。海盗为何如此猖獗?甲乙丙丁四人有如下断定:甲:海盗猖獗的主因是被劫船只的船主通常都愿支付高额赎金。乙:如果海盗猖獗的主因是被劫船主愿支付高额赎金,那么肯定会助长海盗的气
Theearthiswitnessinganurbanrevolution,aspeopleworldwidecrowdintotownsandcities.In1800onlyfivepercentofthew
QueenMary’sReignI.HistoriceventsA.KingHenryVIIIplannedMary,his【T1】_______,tomarryhissonEdward.B.Hermothe
最新回复
(
0
)