首页 > 代码库 > 编程之美2.12 高速寻找满足条件的两个数
编程之美2.12 高速寻找满足条件的两个数
这道题目的意思是,在一个数组中寻找两个数。使这两个数的和等于给定的数(找到随意一组就能够了)。
题目读完之后,感觉这道题目还是非常easy的。就是遍历数组呗,走两遍,即能够在O(n2)时间复杂度内解决问题。
只是,细致想想之后。复杂度还是能够减少的。
首先,我们能够对数组进行排序,这样,得到的数组就是一个有序数组(如果数组是递增的)。那么,我们能够利用两个指针。一个指针指向数组的第一个元素,一个指针指向数组的最后一个元素。所以,就是两个指针分别指向两个最值。然后前后每次移动一个指针就能够尝试的去寻找所须要的一组数。
比方。初始时,两个指针指向的值相加之后,和大于给定的数字,那么。就须要把“最大值指针”向前移动,这样,就会使得两个指针指向的值的和变小;如果两个指针指向的值相加小于给定的数字,那么。就须要把“最小值指针”向后移动。这样,就会使得两个指针指向的值的和变大了。然后,终止条件是两个指针不能相等或者“最小值指针”等于“最大值指针”。
有了上述思想。能够得到例如以下的解决的方法:
函数声明:
/*2.12 高速寻找满足条件的两个数*/ void DutQuickFindSpecifyTwoNums(int*, int, int, int&, int&);
源码:
/*高速寻找两个值*/ bool _DutQuickFindSpecifyTwoNums = false; void DutQuickFindSpecifyTwoNums(int* A, int size, int sum, int& one, int& two) { if (!A || size <= 1) { one = -1; two = -1; return; } std :: sort(A, A + size); int i = 0; int j = size - 1; /*即前后各一个指针。然后两个指针往中间方向走,比对遇到的值*/ while (i < j) { if (A[i] + A[j] == sum) { one = A[i]; two = A[j]; return; } else if (A[i] + A[j] > sum) --j; else ++i; } one = -1; two = -1; return; }
编程之美2.12 高速寻找满足条件的两个数
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。