首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
输入一个已经按升序排序过的数组和一个数字,在数组中查找两个数,使得它们的和正好是输入的那个数字。要求时间复杂度是O(n)。如果有多对数字的和等于输入的数字,输出任意一对即可。 例如输入数组1、2、4、7、11、15和数字15。由于4+11=15,因此输出4
输入一个已经按升序排序过的数组和一个数字,在数组中查找两个数,使得它们的和正好是输入的那个数字。要求时间复杂度是O(n)。如果有多对数字的和等于输入的数字,输出任意一对即可。 例如输入数组1、2、4、7、11、15和数字15。由于4+11=15,因此输出4
admin
2019-03-29
98
问题
输入一个已经按升序排序过的数组和一个数字,在数组中查找两个数,使得它们的和正好是输入的那个数字。要求时间复杂度是O(n)。如果有多对数字的和等于输入的数字,输出任意一对即可。
例如输入数组1、2、4、7、11、15和数字15。由于4+11=15,因此输出4和11。
选项
答案
/////////////////////////////////////////////////////////////////////// // Find two numbers with a sum in a sorted array // Output: ture is found such two numbers, otherwise false /////////////////////////////////////////////////////////////////////// bool FindTwoNumbersWithSum ( int data[], // a sorted array unsigned int length, // the length of the sorted array int sum, // the sum int& num1, // the first number, output int& num2 // the second number, output ) { bool found = false; if(length < 1) return found; int ahead = length - 1; int behind = 0; while(ahead > behind) { long long curSum = data[ahead] + data[behind]; // if the sum of two numbers is equal to the input // we have found them if(curSum == sum) { num1 = data[behind]; num2 = data[ahead]; found = true; break; } // if the sum of two numbers is greater than the input // decrease the greater number else if(curSum > sum) ahead --; // if the sum of two numbers is less than the input // increase the less number else behind ++; } return found; }
解析
如果我们不考虑时间复杂度,最简单想法的莫过去先在数组中固定一个数字,再依次判断数组中剩下的n-1个数字与它的和是不是等于输入的数字。可惜这种思路需要的时间复杂度是O(n2)。
分析:如果我们不考虑时间复杂度,最简单想法的莫过去先在数组中固定一个数字,再依次判断数组中剩下的n-1个数字与它的和是不是等于输入的数字。可惜这种思路需要的时间复杂度是O(n2)。
我们假设现在随便在数组中找到两个数。如果它们的和等于输入的数字,那太好了,我们找到了要找的两个数字;如果小于输入的数字呢?我们希望两个数字的和再大一点。由于数组已经排好序了,我们是不是可以把较小的数字的往后面移动一个数字?因为排在后面的数字要大一些,那么两个数字的和也要大一些,就有可能等于输入的数字了;同样,当两个数字的和大于输入的数字的时候,我们把较大的数字往前移动,因为排在数组前面的数字要小一些,它们的和就有可能等于输入的数字了。
我们把前面的思路整理一下:最初我们找到数组的第一个数字和最后一个数字。当两个数字的和大于输入的数字时,把较大的数字往前移动;当两个数字的和小于数字时,把较小的数字往后移动;当相等时,打完收工。这样扫描的顺序是从数组的两端向数组的中间扫描。
问题是这样的思路是不是正确的呢?这需要严格的数学证明。感兴趣的读者可以自行证明一下。
转载请注明原文地址:https://kaotiyun.com/show/aRmZ777K
0
程序员面试
相关试题推荐
YourfriendDavidjustsentyouabookthatyouexpectedasabirthdaypresent.Sendane-mailtohimtoexpressyourappreciati
AWelcomeE-mail欢迎邮件Someinternationalstudentsarecomingtoyouruniversity.Writethemane-mailinthenameoftheStudent
Inthissection,youareaskedtowriteanessaybasedonthefollowinginformation.Makecommentsandexpressyourownopinion.
输入一个整形数组,数组里有正数也有负数。数组中连续的一个或多个整数组成一个子数组,每个子数组都有一个和。求所有子数组的和的最大值。要求时间复杂度为O(n)。例如输入的数组为1,-2,3,10,-4,7,2,-5,和最大的子数组为3,10,
定义栈的数据结构,要求添加一个min函数,能够得到栈的最小元素。要求函数min、push以及pop的时间复杂度都是O(1)。
触发器分为事前触发和事后触发,这两种触发有和区别。语句级触发和行级触发有何区别。
使用.NETPassport向导注册MSN帐户,姓名为李明,邮件的地址为liming@hotmail.com,密码为123456lm。
在Excel中,函数ABS(ROUND(-1.478,2))的计算结果是()。A.-1.478B.1.48C.-1.48D.1.5
随着网络信息技术的进步和社会信息化程度的不断提高,一个由庞大的网络产业带动,并导致整个经济社会产生巨大变革的数字经济时代已经离我们越来越近。目前,“数字化校园”、“数字企业”、“数字城市”等一系列项目快速上马,在这些项目中,信息的数字化与数字信息的网络传输
在数据库系统中,“事务”是访问数据库并可能更新各种数据项的一个程序执行单元。为了保证数据完整性,要求数据库系统维护事务的原子性、一致性、隔离性和持久性。针对事务的这4种特性,考虑以下的架构设计场景:假设在某一个时刻只有一个活动的事务,为了保证事务
随机试题
《郑伯克段于鄢》的中心意旨是()
关于结肠癌错误的是
男性,32岁。咳嗽气粗,咯大量白黏痰,胸胁胀满而痛,面赤身热,口干欲饮,舌苔黄厚腻,舌质红,脉数。
酸水解速度最快的是
在国际法上,战争开始后______。
履行FOB交货条件下的进口合同,应由()负责派船将货物运到合同规定的目的地。
设备委托监理合同中业主的权利包括()。
依据( )计算得到的估算成本是企业确定投标报价的基础。
国际工程承包合同争议的非诉讼纠纷解决方式一般包括()。
N注册会计师首次审计丑公司2005年度会计报表时,发现前任注册会计师因为2003年开工的一项在建工程对2004年度会计报表出具了保留意见审计报告。互N注册会计师执行外勤审计工作时,该项工程仍未完工。按照相关审计准则对期初余额审计的规定,N注册会计师应执行以
最新回复
(
0
)