首页 > 代码库 > 算法导论学习笔记(3)-习题2.3-7-排序+二分
算法导论学习笔记(3)-习题2.3-7-排序+二分
question(题意):
Describe a O(n lg(n))-time algorithm that, given a set S of n integers and another integer x, determines whether or not there exist two elements in S whose sum is exactly x.
设计一个O(n lg(n))时间复杂度的算法,给定一个n个数字的集合,和一个数字x, 问,是否能在这个集合中找到两个数字,他们的和恰好为x.
Solution(解法):
在一个数组里面找某个数,O(n lg(n)),很容易想到用排序+二分,算法导论刚刚讲了归并排序,正好是O(n lg(n))的排序算法,可是这个题是找两个数的和为x, 那么该如何做呢,我们可以在排序后的数组里面,从小到大一次枚举第一个数(该数字必须满足<=x/2,原因自己想),然后在后面查找是否有另外一个数即可,下面是代码:
Code(代码):
//算法导论 习题2.3-7 #include <iostream> using namespace std; void merge(int* A, int p, int q, int r) { int n1 = q - p +1, n2 = r - q; int L[n1], R[n2]; for (int i = 0; i < n1; i++) L[i] = A[p+i]; for (int i = 0; i < n2; i++) R[i] = A[q+i+1]; int i = 0, j = 0, k = p; while (k <= r) { if (i >= n1) { while (j < n2) { A[k++] = R[j++]; } } else if(j >= n2) { while (i < n1) { A[k++] = L[i++]; } } else if(L[i] <= R[j]) { A[k++] = L[i++]; } else { A[k++] = R[j++]; } } } void merge_sort(int* A, int p, int r) { if (p < r) { int q = (p + r) / 2; merge_sort(A, p, q); merge_sort(A, q+1, r); merge(A, p, q, r); } } bool bSearch(int* A, int L, int R, int v) { while (L <= R) { int M = (L + R) / 2; if (A[M] < v) { L = M+1; } else if (A[M] > v) { R = M-1; } else { return true; } } return false; } bool Find(int* A, int n, int x) { merge_sort(A, 0, n-1); for (int i = 0; i < n; i++) { if (A[i] <= x / 2) { if (bSearch(A, i+1, n-1, x-A[i])) { return true; } } else { return false; } } return false; } int main() { int A[10] = {2, 3, 1, 5, 3, 2, 9, 3, 0, 7}, x; while (cin >> x) { if (Find(A, 10, x)) { cout << "find two numbers whose sum is " << x << endl; } else { cout << "Not find two numbers whose sum is "<< x << endl; } } return 0; }
算法导论学习笔记(3)-习题2.3-7-排序+二分
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。