首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
输入一个按升序排序过的整数数组{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
66
问题
输入一个按升序排序过的整数数组{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://www.kaotiyun.com/show/iYxi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
简述近代香港问题的形成。
日本明治维新和中国戊戌变法一成一败的原因。
简述20世纪30年代英法推行绥靖政策的原因。
下列对凡尔赛和约中有关德国疆界问题的表述,正确是()。
第三次科技革命促进了社会经济结构和社会生活结构的变化,其在社会经济结构方面的变化主要是()
十六国时期的历史,可以划分为前后两个时期,其分界线是()。
关于《新学伪经考》、《孔子改制考》的说法正确的是()。①都是利用古书古人宣传西方资产阶级政治的学说,向西方寻求救国真理②借用儒家学说和孔子的偶像进行宣传,可减少来自封建顽固势力的阻挠和压力③是维新变法的重要理论依据④动摇了封建统治的思想基
8世纪利用汉字偏旁创造日本片假名的是()。
在请求页式系统中,一程序的页面走向(访问串或引用串)为2,3,4,5,2,3,6,2,3,4,5,6,设分配给该程序的存储块数为m。试分别计算m=3和m=4时,FIFO和LRU两种替换算法的缺页(页故障)数,并给出:结果说明了什么?
某32位计算机系统采用段页式虚拟存储管理,现有一个进程被分成5段,其段号和段长见下表,段内分页,页表见下,存放在内存中,每页的长度为4096B。进程运行到某一个指令,其地址为(2,3,010),当前CPU的寄存器和地址加法器的状态如图所示,当上述指令执行时
随机试题
甲公司为一家在深圳证券交易所上市的企业,主要从事饮料包装成套设备的研发、生产和销售。2015年度,甲公司发生的部分业务资料如下:(1)2015年2月5日,甲公司通过全国中小型企业股份转让系统以每股5元的价格购入A公司股票2000万股,取得A公司40%有
下列消费者属于一级消费者的是()
青年男性,2天来胸背部疼痛,今晨出现双下肢无力,伴二便障碍,查脐以下各种感觉障碍,双下肢肌力0级,无病理反射。最可能的诊断是
失范行为是与教育规范不相一致、不协调甚至是冲突的行为。可以划分为:目的取向型失范行为、价值取向型失范行为、情感型失范行为、传统型失范行为这四类理想类型。其中情感型失范行为,主要指为了满足生理、心理或情感上的需要而做出的失范行为。根据上述定义,下列属于情感型
(2015广西33)2013年5月,微博上______着一份百字令微情书。“不尽红笺相思意”,一时感动无数网友争相效仿。整篇文字呈菱形排列,词句婉约,文笔______,从中可以看到作者表达爱情的______。依次填入画横线部分最恰当的一项是:
论述产品如何适应国外市场条件。[河北工业大学2011国际商务硕士]
GUESSCONSULTING121MarketSt.,NewYork,NY10012J.P.Thompson,Esq.14,RueduMontBlanc1201Geneva
Readthebusinesscoverletterbelow.Inmostofthelines(41-52),thereisoneextraword.Iteitherisgrammaticallyincor
Cyberia--InternetCafesEvaPascoeridestoworkonamotorbike.Herbusinesswardrobefeaturessuchitemsasblackleggings,
李先生上个月生了一个男孩。
最新回复
(
0
)