题目:输入一个已经按升序排序过的数组和一个数字,在数组中查找两个数,使得它们的和正好是输入的那个数字。要求时间复杂度是O(n)。如果有多对数字的和等于输入的数字,输出任意一对即可。
例如输入数组1、2、4、7、11、15和数字15。由于4+11=15,因此输出4和11。
分析:如果我们不考虑时间复杂度,最简单想法的莫过去先在数组中固定一个数字,再依次判断数组中剩下的n-1个数字与它的和是不是等于输入的数字。可惜这种思路需要的时间复杂度是O(n2)。
我们假设现在随便在数组中找到两个数。如果它们的和等于输入的数字,那太好了,我们找到了要找的两个数字;如果小于输入的数字呢?我们希望两个数字的和再大一点。由于数组已经排好序了,我们是不是可以把较小的数字的往后面移动一个数字?因为排在后面的数字要大一些,那么两个数字的和也要大一些,就有可能等于输入的数字了;同样,当两个数字的和大于输入的数字的时候,我们把较大的数字往前移动,因为排在数组前面的数字要小一些,它们的和就有可能等于输入的数字了。
我们把前面的思路整理一下:最初我们找到数组的第一个数字和最后一个数字。当两个数字的和大于输入的数字时,把较大的数字往前移动;当两个数字的和小于数字时,把较小的数字往后移动;当相等时,打完收工。这样扫描的顺序是从数组的两端向数组的中间扫描。
问题是这样的思路是不是正确的呢?这需要严格的数学证明。感兴趣的读者可以自行证明一下。
参考代码:
///////////////////////////////////////////////////////////////////////
// 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;
}
发表评论
-
析构函数为虚函数的原因
2012-09-09 11:42 786我们知道,用C++开发的时候,用来做基类的类的析构函数 ... -
hash的应用
2012-08-31 23:02 925第一部分为一道百度面试题Top K算法的详解;第二部分为关 ... -
微软智力题
2012-08-29 19:59 539第一组1.烧一根不均匀的绳,从头烧到尾总共需要1个小时。现在有 ... -
C++不能被继承的类
2012-08-27 20:16 997一个类不能被继承, ... -
括号对齐问题
2012-08-27 10:47 1352解法一:左右括号成一对则抵消 可以 ... -
树的遍历
2012-08-19 10:43 680/****************************** ... -
堆排序
2012-08-16 14:24 844堆:(二叉)堆数据结构是一种数组对象。它可以被视为一棵完全 ... -
多态赋值
2012-08-14 16:16 778#include <iostream> usi ... -
static变量与static函数(转)
2012-08-13 10:15 702一、 static 变量 static变量大致分为三种用法 ... -
不用sizeof判断16位32位
2012-08-10 15:21 1664用C++写个程序,如何判断一个操作系统是16位还是3 ... -
找出连续最长的数字串(百度面试)
2012-08-09 15:15 1112int maxContinuNum(const char*in ... -
顺序栈和链栈
2012-08-06 10:01 767顺序栈:话不多说直接上代码 #include ... -
队列的数组实现和链表实现
2012-08-05 16:20 995话不多少,数组实现上代码: #include<i ... -
KMP算法详解
2012-08-02 21:40 850KMP算法: 是在一个“主文本字符串” ... -
字符串的最长连续重复子串
2012-08-01 15:05 9701两种方法: 循环两次寻找最长的子串: <方法一> ... -
寻找一个字符串连续出现最多的子串的方法(转)
2012-07-31 21:19 919算法描述首先获得后缀数组,然后1.第一行第一个字符a,与第二行 ... -
字符串的循环移位
2012-07-31 16:52 936假设字符串:abcdefg 左循环两位:cdefgab 右 ... -
一次谷歌面试趣事(转)
2012-07-31 15:26 727很多年前我进入硅谷 ... -
约瑟夫环问题(循环链表)
2012-07-30 21:31 1242题目描述:n只猴子要选大王,选举方法如下:所有猴子按 1, ... -
面试之单链表
2012-07-30 20:18 6921、编程实现一个单链表的建立/测长/打印。 ...
相关推荐
给定两个已排序的整数数组nums1和nums2,将nums2合并为nums1作为一个已排序的数组。 在nums1和nums2中初始化的元素数分别为m和n。 您可以假定nums1的大小等于m + n,以使其具有足够的空间来容纳nums2中的其他元素。...
给定两个有序数组a b 使合并后的数组仍然有序 归并算法的事件复杂度为O logn
给定两个整型数组,本题要求找出不是两者共有的元素。 输入格式: 输入分别在两行中给出两个整型数组,每行先给出正整数N(≤20),随后是N个整数,其间以空格分隔。 输出格式: 在一行中按照数字给出的...
文章目录26. 删除排序数组中的重复项题目解题思路代码实现实现结果 26. 删除排序数组中的重复项 ...题目 给定一个排序数组,你需要在 原地 删除...函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。
c++实现二叉树的数组存储,代码很简单,参考即可
二维数组按行求平均值,形成一个新的一维数组
数组排序(VB6.0代码编写)给定一个数组,把不是升序的数据去掉,然后重新赋给另一数组
# 给定两个大小为 m 和 n 的有序数组 nums1 和 nums2 # 请找出这两个有序数组的中位数。要求算法的时间复杂度为 O(log (m+n)) # 你可以假设 nums1 和 nums2 不同时为空 # 示例 1: # nums1 = [1, 3] # nums2 = [2] #...
对于在两个非常大的数组上快速完成相同工作并具有一些附加功能的函数,请参阅 Jos 的 NEARESTPOINT: www.mathworks.com/matlabcentral/fileexchange/8939 左上角的图显示了最大值。 'Vals' 的长度与 'X' 的长度,...
LeetCode 问题 33 是一个关于在旋转排序数组中搜索一个给定目标值的问题。如果目标值存在返回它的索引,否则返回 -1。数组可能在某个未知的轴心上进行了旋转(例如 [0,1,2,4,5,6,7] 可能变成 [4,5,6,7,0,1,2])。你...
# 函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2 # 你不需要考虑数组中超出新长度后面的元素 # 示例 2: # 给定 nums = [0,0,1,1,1,2,2,3,3,4], # 函数应该返回新的长度 5, 并且原数组 nums 的...
函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。 你不需要考虑数组中超出新长度后面的元素。 示例 2: 给定 nums = [0,0,1,1,1,2,2,3,3,4], 函数应该返回新的长度 5, 并且原数组 nums
对于给定的有序数组nums,移除数组中存在的重复数字,确保每个数字只出现一次并返回新数组的长度 注意:不能为新数组申请额外的空间,只允许申请O(1)的额外空间修改输入数组 Example 1: Given nums = [1,1,2], ...
给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。
按奇偶排序数组给定一个非负整数数组 A,返回一个数组,在该数组中, A 的所有偶数元素之后跟着所有奇数元素。示例:输入:[3,1,2,4]输出:[2,4,3,1
PHP array_search() 函数用于在数组中搜索给定的值,如果成功则返回相应的键名,否则返回 FALSE 。 语法: mixed array_search( mixed needle, array array [, bool strict] )参数说明: 参数 说明 needle ...
给定一个数组,数组包含10个整型元素,将其按照从小到大的顺序排列后输出,要求排序的算法用子程序来实现。
使用这个函数可以避免调用 Matlab SORT(),因为两个输入已经排序,所以它做了不必要的工作。 Mex 实现速度。 支持“行”选项
# 搜索一个给定的目标值,如果数组中存在这个目标值,则返回它的索引,否则返回 -1 # 你可以假设数组中不存在重复的元素 # 你的算法时间复杂度必须是 O(log n) 级别 # 示例 1: # 输入: nums = [4,5,6,7,0,1,2], ...
有1个包含N个整数的数组A,定义1个数组的美丽值为数组中所有不同整数的和。求数组A的所有连续子序列的美丽值之和。