首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
输入一个按升序排序过的整数数组{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
94
问题
输入一个按升序排序过的整数数组{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
学硕统考专业
相关试题推荐
二战后期,反法西斯同盟国召开了一系列会议、达成了一系列协议,以解决战后世界的安排问题,这些会议中以()最为重要,所以,我们将二战后的国际关系格局称为()。
西汉初年,西域共有36国,其中以()人口最多。
晚清时期清帝年号的正确排序是()
中华人民共和国恢复了在联合国合法席位的时间是()。
埃及曾两次被波斯帝国征服,波斯第二次征服埃及的时间是()。
解放军渡江战役中横渡长江的东西两个攻击点是()。
印度种姓制度中,处于被剥削被压迫地位的两个瓦尔那是()①婆罗门②刹帝利③首陀罗④吠舍
下列哪两个国家是第二次工业革命的发源地和“中心”?
北约和华约两个组织对峙近半个世纪,这()。
在请求分页存储管理中,若采用FIFO的页面淘汰算法,当分配的页面数增加时,缺页中断的次数()。
随机试题
A.近端小管B.髓袢降支C.髓袢升支粗段D.远端小管和集合管E.输尿管Cl-的继发主动转运是在()。
Imaginethemostfamouspersonyouknow,MichaelJordan,BritneySpears,PrinceWilliam.Nowthinkofthis:Notoneofthemisa
关于功能失调性子宫出血,正确的是
男,35岁,化工厂工人,工作中不小心吸入有毒气体后出现恶心、呕吐及震颤,急诊来诊。查体:皮肤口唇呈樱桃红色,呼出气体有苦杏仁味。最可能的诊断为
A、总水分B、结合水C、非结合水D、自由水E、平衡水物料表面的水分是()
国家重视中药材资源的保护、利用和可持续发展,加强中药材野生资源的采集和抚育管理,以下关于中药材的生产、经营和使用管理说法错误的是
检验检疫机构可根据需要,对检验合格的进出口商品加施检验检疫标志或封识。 ( )
下列各项中,属于期望投资报酬率的构成内容的有()。
“头顶马聚源,脚踩内联升,身穿瑞蚨祥,腰缠四大恒”,这首老北京民谣形象地反映了老字号在市场心目中的地位。荣宝斋的字画、享得利的钟表、月盛斋的酱肉、张一元的茶叶、十八街的麻花、狗不理的包子……这些耳熟能详的老字号,构成了人们对悠悠岁月的珍贵记忆。这段文字主
再社会化(南开大学)
最新回复
(
0
)