首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
输入一个按升序排序过的整数数组{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
69
问题
输入一个按升序排序过的整数数组{1、2、4、7、11、15}以及一个整数数字15，可以从该数组中找到两个数字，即4和11，使得4+11=15。请实现一个时间上尽可能高效率的算法，输入一个已经按升序排序过的整数数组和一个整数数字，在数组中查找两个数，使得它们的和正好是输入的那个整数数字。如果有多对数字的和等于输入的整数数字，输出任意一对即可。要求：
给出算法的基本设计思想。
选项
答案
基本设计思想：如果不考虑时间复杂度，最简单的想法是先在数组中固定一个数字，再依次判断数组中剩下的n—1个数字与它的和是不是等于输入的数字。可惜这种思路需要的时间复杂度是O(n
2
)，不满足题意要求。 假设现在随便在数组中找到两个数，如果它们的和等于输入的数字，则找到了要找的两个数字；如果小于输入的数字呢，则希望两个数字的和再大一点。当两个数字的和大于输入的数字的时候，把较大的数字往前移动，因为排在数组前面的数字要小一些，它们的和就有可能等于输入的数字了。 把前面的思路整理一下：找到数组的第一个数字和最后一个数字。当两个数字的和大于输入的数字时，把较大的数字往前移动；当两个数字的和小于数字时，把较小的数字往后移动；当相等时，正合题意。
解析
转载请注明原文地址:https://www.kaotiyun.com/show/4Yxi777K
本试题收录于：
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
论述清末新政的失败原因及其意义。
试分析第二次世界大战的历史地位。
1938年，英、法、德、意在德国召开会议讨论对捷克斯洛伐克的苏台德地区的问题，这次会议被称为()，它把英法的绥靖政策推到了顶峰，加速了二战的爆发。
清初设置的两个“办事大臣”是()。①宁古塔②西宁③库伦④西藏
()后，辽东局势起了根本变化，明朝在军事上失去主动进攻的力量，而后金则由防御转入进攻。
日本在《二十一条》中提出：“中国沿海岛屿不得租于他国。”其真实目的是()。
二战后期，反法西斯同盟国召开了一系列会议、达成了一系列协议，以解决战后世界的安排问题，这些会议中以()最为重要，所以，我们将二战后的国际关系格局称为()。
“二战”后主要资本主义国家经济恢复和发展的杠杆是()。①政府采取宏观调控政策②发展国家垄断资本主义③充分利用科技成果④加强国际经济联系
某系统中n个相互独立的生产者进程为一个消费者进程提供数据，假设每个生产者提供的数据写入各不相同的缓冲区，且生产者写缓冲区的速度比消费者读缓冲区的速度快，则缓冲区个数的最优值应为()。
荷兰国旗问题：设有一个仅红、白、蓝三种颜色的条块组成的条块序列，请编写一个时间复杂度为O(n)的算法，使得这些条块按红、白、蓝的顺序排好，即排成荷兰国旗图案。
随机试题
发生于结肠的疾病有
Q—CDMA(IS-95)系统工作于()MHz频段。
输卵管外侧端的开口部位在【】
Wegener肉芽肿主要导致
实行终身负责制的工程包括()。
对于个人汽车贷款贷前调查的表述，错误的是()。
399题版MMPI是为()。
1923年6月中共三大的召开标志着国共第一次合作的正式形成。()
利润转化为平均利润的过程，就是
设a＝(1，－1，2)T，β＝(2，1，1)T，A＝αβT，则An＝______．
最新回复
(
0
)
