首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
输入一个按升序排序过的整数数组{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
50
问题
输入一个按升序排序过的整数数组{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
学硕统考专业
相关试题推荐
【波兹南事件】北京大学2003年欧美近现代史真题;华中师范大学2015年世界史基础真题
水门事件
十六国时期的历史,可以划分为前后两个时期,其分界线是()。
唐朝对外关系呈现出前所未有的盛况,其原因不包括()
宁夏回族自治区的设立时间是()。
北约和华约两个组织对峙近半个世纪,其影响是()。
试分析淝水之战前后南北政局的特点及其变化。
1854年,英国外交大臣致函英国驻华公使说:“为了适应外商对农业产品已增加了的需要,新的贸易市场尚待开辟。”1856年,法国外长则指令法国驻华代办强调“商业关系的推广”,并强调“这是一个关系到至高无上权益的问题”。这说明()。
随机试题
蝶阀应装在管道法兰的正中间,以防止阀瓣碰到管道而损坏阀瓣或轴。()
日耳曼法为严格保护债权人的利益,保证债务履行经常使用的方法是()
Word2000默认的中文字体是_______,默认的字号是五号。
雌激素的生理功能不包括下列哪项
下列有关肺的描述,正确的是
兴奋性突触后电位是指在突触后膜上发生的电位变化为
美国福克斯波罗公司当年为了生存急需新技术成果,一位工程师拿着新产品研制样品送给经理,经理看到该产品的巧妙设计很惊喜,就在自己的抽屉东翻西找,最后终于找到了一只香蕉,满怀激情地对这位工程师说:“伙计,给你!”这位工程师倍受感动。经理给予工程师一只香蕉还可
下列各项中,应计入建造合同收入的有()。
根据人口普查条例的规定,公民有义务如实填报人口普查信息;普查机构有责任对公民填报的个人资料严格保密,决不用于普查以外的任何目的。这说明()。
下列有关类继承的叙述中,错误的是()。
最新回复
(
0
)