|
http://blog.csdn.net/yuucyf/article/details/6407926 http://www.cnblogs.com/caidaxia/archive/2011/11/02/2232802.html http://blog.csdn.net/v_july_v/article/details/6419466 最优分析：程序员编程艺术第五章 题目：输入一个已经按升序排序过的数组和一个数字，在数组中查找两个数，使得它们的和正好是输入的那个数字。要求时间复杂度是O(n)。如果有多对数字的和等于输入的数字，输出任意一对即可。 例如输入数组1、2、4、7、11、15和数字15。由于4+11=15，因此输出4和11。 分析：如果我们不考虑时间复杂度，最简单想法的莫过去先在数组中固定一个数字，再依次判断数组中剩下的n-1个数字与它的和是不是等于输入的数字。可惜这种思路需要的时间复杂度是O(n2)。 我们假设现在随便在数组中找到两个数。如果它们的和等于输入的数字，那太好了，我们找到了要找的两个数字；如果小于输入的数字呢？我们希望两个数字的和再大一点。由于数组已经排好序了，我们是不是可以把较小的数字的往后面移动一个数字？因为排在后面的数字要大一些，那么两个数字的和也要大一些，就有可能等于输入的数字了；同样，当两个数字的和大于输入的数字的时候，我们把较大的数字往前移动，因为排在数组前面的数字要小一些，它们的和就有可能等于输入的数字了。 我们把前面的思路整理一下： 方法一： 最初我们找到数组的第一个数字和最后一个数字。当两个数字的和大于输入的数字时，把较大的数字往前移动；当两个数字的和小于数字时，把较小的数字往后移动；当相等时，打完收工。这样扫描的顺序是从数组的两端向数组的中间扫描。 问题是这样的思路是不是正确的呢？这需要严格的数学证明。感兴趣的读者可以自行证明一下。 方法二： 描述： 输入一个已经按升序排序过的数组A[N]和一个数字K。 在数组中查找两个数A[i]和A[j]，使得它们的和正好是输入的那个数字A[i]+A[j]=K。 要求时间复杂度是O(n)。如果有多对数字的和等于输入的数字，输出任意一对即可。 例如输入数组1、2、4、7、11、15和数字15。由于4+11=15，因此输出4和11。 解法： 设置两个数组下标 i 和 j， i 指向数组中未被遍历过的最小元素，初始值 i = 0， j 指向数组中未被遍历过的最大元素，初始值 j = N - 1 当i < j时，循环执行下列操作： (1) 若 A[i] + A[j] = K，则输出 A[i] 和 A[j] (2) 若 A[i] + A[j] < K, 则 i++ (3) 若 A[i] + A[j] > K, 则 j-- 循环结束时，如果没有找到和为K的两个元素，则报告未找到。 输入一个已经按升序排序过的数组和一个数字sum，在数组中查找两个数，使得它们 的和正好是输入的那个数字sum，要求时间复杂度为O(n) 解题思路：设置头尾两个指针，从第一个元素和最后一个 元素相加，如果大于sum,则尾指针向前移1个元素，继续判断两个数的和； 如果小于sum，则头指针向后移1个元素，继续判断两个数的和 include using namespace std; void FindNum(int* array,int length, int sum) int *begin=&array[0]; int *end=&array[length-1]; while (begin<end)< p=""> if ((*begin+*end)>sum) end--; else if ((*begin+*end)<sum)< p=""> begin++; else cout<<*begin<<""<<*end<<endl;< p=""> return; cout<<"cannot find"<<endl;< p=""> int main() int array[]=1,2,4,7,11,15; FindNum(array,6,11); return 0; |
|
|
