输入一个按升序排序过的整数数组{1、2、4、7、11、15}以及一个整数数字15，我们可以从该数组中找到两个数字，即4和11，使得4+11=15。请实现一个时间上尽可能高效率的算法，当输入一个已经按升序排序过的整数数组和一个整数数字，在数组中查找两个数，使

admin2017-11-20 93

问题输入一个按升序排序过的整数数组{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/9VRi777K

本试题收录于：计算机408题库学硕统考专业分类

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

计算机408

学硕统考专业

1994年5月，江泽民在进一步强调正确处理改革、发展、稳定的关系时指出()。

毛泽东认为，社会主义这个阶段可分为两个阶段，包括()。

唐朝对外关系呈现出前所未有的盛况，其原因不包括()

与前两次工业革命相比，第三次科技革命在能源结构上的主要变化是()

试析淝水之战前后南北政权的特点和变化。

解放军渡江战役中横渡长江的东西两个攻击点是()。

1984年，《中共中央关于经济体制改革的决定》中强调，商品经济的充分发展是社会经济发展不可逾越的阶段，市场调节的辅助性作用不可缺少，并指出要有步骤地逐步缩小指令性计划的范围。这表明当时我国()

印度种姓制度中，处于被剥削被压迫地位的两个瓦尔那是()①婆罗门②刹帝利③首陀罗④吠舍

27岁产妇，体温逐渐升高达38．5℃以上，随后出现面色潮红、胸闷、脉搏增快、呼吸急促、口渴、痱子布满全身，考虑为

A、伤寒B、钩端螺旋体病C、恙虫病D、肾综合征出血热E、地方性斑疹伤寒女性，23岁，高热8天，伴有畏寒、头痛、全身酸痛。体检：胸腹部可见少量散在淡红色小斑丘疹，肝、脾均在肋下1cm。血WBC2.8×109／L，外斐反应1：

A．D-木糖B．苦杏仁苷C．D-果糖D．槐糖E．洋地黄毒苷属于五碳醛糖的是()。

下列关于公务员回避的说法哪项是正确的?()

2007年以来，由于国内的消费物价指数屡创新高，中国人民银行从2007年3月18日开始连续6次加息，金融机构一年期存款基准利率由2．52％升至4．14％，预期未来利率水平仍将上升，此时的理财策略调整建议可以采取()。

县级以上地方人民政府应当根据当地的经济发展水平、区位优势和资源条件，按照()的原则，有重点地推进农村小城镇建设。

很多大学生希望毕业后找到一份工作，稳步发展，可是也有许多人不愿_______。他们有相对稳定的家庭背景，有工作能力，却在寻找生活的另一种可能性。填入画横线部分最恰当的一项是：

根据婚姻法的有关规定，下列有关离婚的表述，正确的有()。

下列程序的功能是为变量赋值，程序运行后，输出i=51。请改动main方法中的错误，使程序能够正确编译、运行并输出正确的结果。注意：不改动程序结构。classA{privateinta;