首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
输入一个按升序排序过的整数数组{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
67
问题
输入一个按升序排序过的整数数组{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
学硕统考专业
相关试题推荐
试论述五四运动以后中国社会民族矛盾与阶级矛盾交替变化。
1939年8月23日,苏德双方签了()和《秘密附属议定书》,划定了双方在东欧的势力范围。这一条约使德国得以进攻波兰,使第二次世界大战终于爆发。
在努力纠正“文化大革命”错误的过程中,遇到的严重障碍是()
()是解放战争时期西北战场的关键一次战役,是西北战局的转折点。
战国初期,上党地区在下列哪一个国家的控制范围之内?()
根据地理大发现、文艺复兴和宗教改革等重大事件,阐述西欧地区在15—16世纪发生的历史性转变。
“瓜步之战”发生在下列哪两个政权之间?()
阅读史料回答以下问题:天既哀大地生人之多艰,黑帝乃降精而救民患,为神明,为圣王,为万世作师,为万民作保,为大地教主。生于乱世,乃据乱世而立三世之法,而垂精太平。乃因其所生之国,而立三世之义,而注意于大地远近、大小若一之大一统。乃立元以统天,以天为
在请求页式系统中,一程序的页面走向(访问串或引用串)为2,3,4,5,2,3,6,2,3,4,5,6,设分配给该程序的存储块数为m。试分别计算m=3和m=4时,FIFO和LRU两种替换算法的缺页(页故障)数,并给出:结果说明了什么?
在一个8级中断的系统中,硬件中断响应从高到低的优先顺序是1→2→3→4→5→6→7→8,通过中断屏蔽技术,将中断处理优先顺序设置为1→3→5→7→2→4→6→8,如果CPU在执行一个应用程序时有5、6、7、8级的四个中断同时到达,CPU在按优先顺序处理到第
随机试题
利益或对利益的满足是相互依赖的,产生这种依赖性的最基本的原因是()
破伤风病人的治疗原则是()
A/泌氢及氨生成减少B/近曲小管重吸收碳酸氢盐降低C/远曲及近曲小管功能均有障碍D/代谢性酸中毒合并高血钾E/H+吸收减少Ⅲ型肾小管性酸中毒
【背景资料】某施工企业为公路工程施工总承包一级企业,注册资金为1.2亿。该公司拟投标承包某公路工程项目,该公路工程按高速公路标准设计,设计行车时速100km,填土路基、填隙碎石底基层、无机结合料基层、沥青混凝土面层,双向四车道。该公路工程拟投资35亿。问
关于粉煤灰路堤的施工,正确的说法是()。
职务侵占罪与贪污罪的区别不包括()。(2012年下半年)
下列关于嘉兴的旅游线路对应正确的有()。
在人员录用原则中,()强调用人既然要用,就一定要明确授权,放手大胆使用,使他充分发挥才干。
2014年10月份,社会消费品零售总额23967亿元,同比名义增长11.5%(扣除价格因素实际增长10.8%,以下除特殊说明外均为名义增长)。其中,限额以上单位消费品零售额11745亿元,增长8.3%。1—10月份,社会消费品零售总额213118亿元,同比
下列选项中,表述错误的是()。
最新回复
(
0
)