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

admin2017-11-20 32

问题输入一个按升序排序过的整数数组{1、2、4、7、11、15}以及一个整数数字15，我们可以从该数组中找到两个数字，即4和11，使得4+11=15。请实现一个时间上尽可能高效率的算法，当输入一个已经按升序排序过的整数数组和一个整数数字，在数组中查找两个数，使得它们的和正好是输入的那个整数数字。如果有多对数字的和等于输入的整数数字，输出任意一对即可。要求：
给出算法的基本设计思想。

选项

答案基本设计思想：如果我们不考虑时间复杂度，最简单的想法是先在数组中固定一个数字，再依次判断数组中剩下的n-1个数字与它的和是不是等于输入的数字。可惜这种思路需要的时间复杂度是O(n²)，不满足题意要求。假设现在随便在数组中找到两个数，如果它们的和等于输入的数字，那太好了，我们找到了要找的两个数字；如果小于输入的数字呢?我们希望两个数字的和再大一点。由于数组已经排好序了，我们是不是可以把较小的数字往后面移动一个数字?因为排在后面的数字要大一些，那么两个数字的和也要大一些，就有可能等于输入的数字了；同样，当两个数字的和大于输入的数字的时候，我们把较大的数字往前移动，因为排在数组前面的数字要小一些，它们的和就有可能等于输入的数字了。我们把前面的思路整理一下：最初我们找到数组的第一个数字和最后一个数字。当两个数字的和大于输入的数字时，把较大的数字往前移动；当两个数字的和小于数字时，把较小的数字往后移动；当相等时，正合题意。

解析

转载请注明原文地址:https://jikaoti.com/ti/qLfjFFFM

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

计算机408

学硕统考专业

在下列我国建国之后的外交活动中，能够体现“和而不同”思想的有()①亚非会议主张“求同存异”②提出“和平共处五项原则”③中日关系实现正常化④同第三世界国家建立友谊

西汉初年，西域共有36国，其中以()人口最多。

战国时期的著名水利工程“郑国渠”位于今天的()。

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

十六国时期的历史，可以划分为前后两个时期，其分界线是()。

中华人民共和国恢复了在联合国合法席位的时间是()。

埃及曾两次被波斯帝国征服，波斯第二次征服埃及的时间是()。

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

我国《著作权法》对于著作权的限制做了很多规定，合理使用是其中之一。下列行为中属于合理使用的是()

关于特征X线的叙述，正确的是

患者，男，60岁。患慢性支气管炎、阻塞性肺气肿合并阻塞性肺疾病10余年，近2天因天气突然变化，患者出现咳嗽、咳痰、气喘等症状。入院检查：呼吸30次／min，SaO288％。血气分析结果：PaO250mmHg，PCO260mmHg。该患者缺氧的类型为

房地产开发企业是(),具有()的经济实体。

某500kV变电所工程，550kV避雷器操作冲击残压Uc为825kV，分别计算出500kV电压互感器、电流互感器的相对地和相间操作冲击耐受电压。相间操作冲击耐受电压不小于下列何项数值的要求?

根据现行国家标准《自动喷水灭火系统施工及验收规范》(GB50261—2017)对自动喷水灭火系统报警阀组进行调试，下列调试结果中，不符合现行国家标准要求的是()。

下列不属于市场经济基本功能的是()。

第二代计算机使用的电子元件是______。