首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
输入一个按升序排序过的整数数组{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
22
问题
输入一个按升序排序过的整数数组{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
学硕统考专业
相关试题推荐
万历年间,()的获得使得佃农与地主之间只存在单纯的经济强制关系,没有人身依附关系
十六国时期的历史,可以划分为前后两个时期,其分界线是()。
在巴黎和会上获利最大的两个国家是()。
洪武年间修复过的水利工程有()。
1973年,以美元为中心的资本主义世界货币体系崩溃,反映出()。①国际金融领域内美元地位衰落②美国由债权国变为债务国③资本主义国家实力的对比发生了新的变化④美国的世界经济地位严重动摇
北约和华约两个组织对峙近半个世纪,其影响是()。
第二次工业革命引起的生产关系方面最突出的变化是()。
解放军渡江战役中横渡长江的东西两个攻击点是()。
解放军渡江战役中横渡长江的东西两个攻击点是()。
随机试题
A.慢性中性粒细胞性白血病B.急性早幼粒细胞性白血病C.急性淋巴细胞性白血病D.慢性粒单核细胞性白血病E.急性单核细胞性白血病化疗过程中易发生或加重DIC的是
做清洁中段尿培养时,以下哪项不正确
下列关于法治与法制的表述哪些是不适当的?()
35kV及以上供电电压允许偏差,在供电部门与用户产权分界处或在供用电协议所规定的电能计量点处考核,为()。
下列关于有限合伙企业和普通合伙企业的区别,说法正确的有( )。
根据我国宪法修正案,在爱国统一战线中新增加的社会阶层是()。
你到一个新单位,你的上司很平庸。你会如何做?
甲为一乘客(老烟民,熟知烟的价格),乙为一小商贩。乙在火车车厢上叫卖:“红塔山香烟,10元钱一条”,甲欣然买之。经查,该烟为假烟,甲与乙之间的行为性质应如何认定()。
TheBeijingPeaceInternationalHotelWeoffertravelersawealthoffeaturesthatpromptreturnvisit.EASYACC
Withexams______,it’sagoodideatoreviewyourclassnotes.
最新回复
(
0
)