首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
输入一个按升序排序过的整数数组{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
53
问题
输入一个按升序排序过的整数数组{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
学硕统考专业
相关试题推荐
下列事件最能体现对苏联民主制造成重大破坏的是()。
明朝初加强专制统治的措施中,与后来宦官专权有直接关系的是()。
十六国时期的历史,可以划分为前后两个时期,其分界线是()。
第二次世界大战后,国际关系最大的变化是()。
试分析淝水之战前后南北政局的特点及其变化。
1984年,《中共中央关于经济体制改革的决定》中强调,商品经济的充分发展是社会经济发展不可逾越的阶段,市场调节的辅助性作用不可缺少,并指出要有步骤地逐步缩小指令性计划的范围。这表明当时我国()
解放军渡江战役中横渡长江的东西两个攻击点是()。
北约和华约两个组织对峙近半个世纪,这()。
下图所示为双总线结构机器的数据通路,IR为指令寄存器,PC为程序计数器(具有自增功能),M为主存(受R/W信号控制),AR为地址寄存器,DR为数据缓冲寄存器,ALU由加、减控制信号决定完成何种操作,控制信号G控制的是一个门电路。另外,线上标注有小圈表示有控
随机试题
“大数据”是当前众多领域关注和应用的热门话题,下列关于“大数据”特点的叙述,正确的有_______。
她在英语演讲中得了一等奖,感到非常兴奋。
蛔虫病的辨证纲领是
在建设项目合理利用资源,节约能源,提高土地利用率中,应充分利用()。
设备监理人员安装设备的重要性分类,采用书面查询、现场调查等方式对供应商或分供商就( )进行调查。
资产信息资料,按信息来源可分为()。
甲公司购进一台价值120万元的机器设备,向保险公司投保。保险合同约定保险金额为60万元,但未约定保险金的计算方法,后保险期间发生了保险事故,造成该设备实际损失80万元;甲公司为防止损失的扩大,花费了6万元施救费。根据保险法律制度的规定,保险公司应当支付给甲
加工橘子罐头,采用酸碱处理脱去中果皮(橘络)会产生严重污染。目前使用酶解法去除橘络可减少污染,下列生长在特定环境下的4类微生物可以大量产生所用酶的有()。
甲企业与乙银行签订借款合同,借款金额为10万元人民币,借款期限为1年,由丙企业作为借款保证人。合同签订3个月后,甲企业因扩大生产规模急需资金,遂与乙银行协商,将贷款金额增加到15万元,甲和银行通知了丙企业,丙企业未予答复。后甲企业到期不能偿还债务。该案中的
在课程评价模式中,认为教育活动中所需的评价应该是广义的,应有助于方案的改进,不限于确定目标是否达成,评价的最大目的在于为学校行政人员、校方领导以及学校的教师们提供信息,以便在必要时对方案加以修订的是()
最新回复
(
0
)