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

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

admin2017-04-28  44
问题 输入一个按升序排序过的整数数组{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题库学硕统考专业分类
0

计算机408

学硕统考专业

相关试题推荐
随机试题
最新回复(0)