首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
输入一个按升序排序过的整数数组{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
76
问题
输入一个按升序排序过的整数数组{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
学硕统考专业
相关试题推荐
十六国时期的历史,可以划分为前后两个时期,其分界线是()。
康有为在他的《孔子改制考》中将孔子奉为主张变革的先驱,下列描述正确的是()
晚清时期清帝年号的正确排序是()
唐朝对外关系呈现出前所未有的盛况,其原因不包括()
巴黎和会上,英美主张把原德国在山东的权利转让给日本,华盛顿会议又表示支持中国让日本归还山东的要求,英美态度发生变化的根本原因是()。
解放军渡江战役中横渡长江的东西两个攻击点是()。
晚清时期清帝年号的正确排序是
解放军渡江战役中横渡长江的东西两个攻击点是()。
1854年,英国外交大臣致函英国驻华公使说:“为了适应外商对农业产品已增加了的需要,新的贸易市场尚待开辟。”1856年,法国外长则指令法国驻华代办强调“商业关系的推广”,并强调“这是一个关系到至高无上权益的问题”。这说明()。
在请求分页存储管理中,若采用FIFO的页面淘汰算法,当分配的页面数增加时,缺页中断的次数()。
随机试题
为防止气孔的产生,碱性低氢型焊条的烘干温度为()。
吕某,男,65岁。平素不耐风寒,极易感冒。近半月来汗出恶风,动则益甚,体倦乏力,面色少华,苔薄白,脉细弱。其证型是
增感屏保护层的作用是
()是我国进口设备采用最多的一种货价。
敞开式循环冷却水系统一般由冷却水用水设备、冷却塔、给水设施、循环水泵、()等组成。
组织结构三要素不包括()。
某铅锌矿2008年销售铅锌矿原矿80000吨,另外移送入选精矿30000吨,选矿比为30%。当地适用的单位税额为2元/吨,该矿当年应缴纳资源税()万元。
课堂提问的()原则提倡,提问的问题不能太大、太空,更不能歧路亡羊,留有岔路口。
在T-SQL中,能够实现分情况显示不同类型数据的函数是【5】。
A、Themanneedsmoreskills.B、Vocabularyissufficientforcommunication.C、Themanshouldpracticeusingthevocabulary.D、Voc
最新回复
(
0
)