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

admin2014-04-17 35

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

选项

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

解析

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

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

计算机408

学硕统考专业

二战期间，下列四次战役的时间先后顺序是()①莫斯科战役②诺曼底登陆③不列颠之战④阿拉曼战役

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

对三国鼎立局面的形成起到关键性作用的战役是()。

1946年5月，中共中央发布的实现“耕者有其田”政策的重要文件是()。

毛泽东认为，社会主义这个阶段可分为两个阶段，包括()。

为加强君权，皇太极时代开始直接控制的“上三旗”不包括()。

“二战”后主要资本主义国家经济恢复和发展的杠杆是()。①政府采取宏观调控政策②发展国家垄断资本主义③充分利用科技成果④加强国际经济联系

北宋在统一南方割据势力的过程中特设()，把征南所得的财富统一存放，以作日后恢复幽燕之费。

以下关于图的说法正确的是()。．I在一个有向图的拓扑序列中，若顶点a在顶点b之前，则图中必有一条弧Ⅱ若一个有向图的邻接矩阵中对角线一下元素均为O，则该图的拓扑序列必定存在Ⅲ在．AOE网中一定只有一条

下列火焰温度最高的火焰是()。

属于Ⅲ型超敏反应的疾病是

在静脉采血时，操作错误的是

血液的生成与何脏关系最密切?

肾病综合征出血热休克期，下列哪种药物不宜首先使用

某孕妇婚后5年，第一次怀孕。目前停经49天，阴道有少量出血，下腹部轻微疼痛，妇检阴道少量血性分泌物，子宫大小符合孕周。宫口闭，血HCG(+)。该孕妇最可能的诊断是

向不特定对象公开募集股份,最近3个会计年度加权平均净资产收益率平均不低于()。

根据《合伙企业法》的规定，普通合伙企业的合伙人发生的下列情形中，属于协议退伙的有()。

()是反映青少年骨骼生长发育和纵向高度的主要形态指标。

在初诊接待中心理咨询员应有的仪态包括()。