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

admin2017-04-28 58

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

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

计算机408

学硕统考专业

利玛窦与徐光启合作翻译的()，介绍了曾经流行于欧洲的欧几里得平面几何的系统理论，大大地丰富了中国古代几何学的内容。

中共十四届六中全会《关于加强社会主义精神文明建设若干重要问题的决议》，强调要()。

中世纪著名的阿拉伯学者阿维森纳的代表作是()。

在1875年宪法中关于法国立法权的叙述，不正确的是()。

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

在西欧列强海外殖民扩张进程中，各国之间相互争夺海上霸权。18世纪末，英国在争霸中取得胜利的根本原因在于()

下列哪两个国家是第二次工业革命的发源地和“中心”?

某计算机有五级中断L4～L0，中断屏蔽字为M4M3M2M1M0，Mi=1(0≤i≤4)表示对Li级中断进行屏蔽。若中断响应优先级从高到低的顺序是L4→L0→L2→L1→L3，则L1的中断处理程序中设置的中断屏蔽字是____。

生产过程中的加热用火、维修焊接用火及其他火源是导致火灾爆炸最常见的原因。焊割作业时必须注意操作，下列说法中，正确的是()。

女，10个月，发热，咳嗽，声音嘶哑1天。查体闻及犬吠样咳嗽及喉鸣音，双肺呼吸音清。最可能的诊断是

骨折后功能锻炼的原则和注意事项，哪一项目描述不正确()

中和病毒作用是P因子对其有稳定作用是

在下列患者中表示特级护理的是

以下各项中，属于营业税征税范围的有()。

以下几个数中，相等的数有()。

试述春秋时期各诸侯国公布成文法的情况，并评价成文法公布的意义。

下列叙述中，正确的是______。