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

admin2017-11-20 75

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

学硕统考专业

1917年发生的开辟人类历史新纪元的重大事件是()。

康有为在他的《孔子改制考》中将孔子奉为主张变革的先驱，下列描述正确的是()

第二次世界大战后，国际关系最大的变化是()。

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

北约和华约两个组织对峙近半个世纪，其影响是()。

“瓜步之战”发生在下列哪两个政权之间?()

下列关于流水施工参数的说法中，错误的有()。

下列关于几寸的说法错误的是()。

We’vespentsomuchonadvertisements,buttheresultsarenot().

我国《商业银行法》规定，商业银行贷款应当遵守资产负债比例管理的规定。其中，贷款余额与存款余额的比例不得超过()。

关于性道德，以下说法正确的是()。

中国古代的“礼”“乐”“射”“御”“书”“数”统称为___________。

当数据库系统出现故障时，通过数据库日志文件可以对数据库数据进行恢复。下列关于数据库日志文件的说法，错误的是()。

在面向对象方法中，类之间共享属性和操作的机制称为【　】。

—ThisisEnglishDepartmentofBeijingUniversity.—Hi,I’mastudentinEnglishDepartment.Ineedtoknowtheforeignprofesso

计算机408

学硕统考专业

1917年发生的开辟人类历史新纪元的重大事件是()。

康有为在他的《孔子改制考》中将孔子奉为主张变革的先驱，下列描述正确的是()

第二次世界大战后，国际关系最大的变化是()。

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

北约和华约两个组织对峙近半个世纪，其影响是()。

“瓜步之战”发生在下列哪两个政权之间?()

下列关于流水施工参数的说法中，错误的有()。

下列关于几寸的说法错误的是()。

We’vespentsomuchonadvertisements,buttheresultsarenot().

我国《商业银行法》规定，商业银行贷款应当遵守资产负债比例管理的规定。其中，贷款余额与存款余额的比例不得超过()。

关于性道德，以下说法正确的是()。

中国古代的“礼”“乐”“射”“御”“书”“数”统称为___________。

当数据库系统出现故障时，通过数据库日志文件可以对数据库数据进行恢复。下列关于数据库日志文件的说法，错误的是()。

在面向对象方法中，类之间共享属性和操作的机制称为【 】。

—ThisisEnglishDepartmentofBeijingUniversity.—Hi,I’mastudentinEnglishDepartment.Ineedtoknowtheforeignprofesso

在面向对象方法中，类之间共享属性和操作的机制称为【　】。