求解所有集合中和为给定值的组合

96 阅读 0 评论 64 点赞

我是靠谱客的博主丰富老鼠，最近开发中收集的这篇文章主要介绍求解所有集合中和为给定值的组合，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

问题描述：

给定一个由n个整数构成的集合S和另一个整数x，求解S中所有的两个数的组合，其和为x

算法分析：

首先通过Merge Sort进行排序，复杂度：O(NlgN)

然后利用Binary search查找x- s[i]，这里需要一个循环来遍历整个集合，所以复杂度为N*O(lgN)= O(NlgN)

整个算法的复杂度为：O(NlgN)

C++实现代码如下：

#include <iostream> using namespace std; void Merge(int A[], int begin, int middle, int end); void MergeSort(int B[], int begin, int end); int BinarySarch(const int D[], int begin, int end, const int &elem); int main() { int x; int size; cout << "Input the size of the array:" << endl; cin >> size; int *a = new int[size] (); cout << "Input the numbers:" << endl; for (int i = 0; i < size; i++) { cin >> a[i]; //b[i] = a[i]; } cout << "Input X:" << endl; cin >> x; MergeSort(a, 0, size - 1); cout << "After MergeSort" <<endl; for (int i = 0; i < size; i++) { cout << a[i] << " "; } cout << endl; for (int i = 0; i < size; i++) { if (a[i] <= x / 2) { int value = x - a[i]; int temp = BinarySarch(a, 0, size -1, value); if (temp != -1 && temp != i) { cout << a[i] << "+" << a[temp] << "=" << x <<endl; } } } delete []a; } /************************************************* Function: BinarySarch Description:在已经从大到小排序的数组中查找某个元素的位置 Input: A:ElementType类型的数组 begin:查找的开始位置 end:查找的结束始位置 elem:所查找的元素 *************************************************/ int BinarySarch(const int D[], int begin, int end, const int &elem) { int middle = (begin + end) / 2; while ( (end - begin) >= 2) { if (D[middle] == elem) { return middle; } else if (D[middle] > elem) { begin = middle; } else { end = middle; } middle = (begin + end) / 2; } if (D[begin] == elem) { return begin; } else if (D[end] == elem) { return end; } else return -1; } /************************************************* Function: Merge Description:合并数组的两已排序的子数组 Input: A:ElementType类型的数组 begin:需要合并的子数组A的开始序号 middle:需要合并的子数组A的结束序号 end:需要合并的子数组B的结束序号 Others: middle + 1 为子数组的开始序号 *************************************************/ void Merge(int A[], int begin, int middle, int end) { int pa = begin; //point to 子数组A int pb = middle + 1; //point to 字数组B int *tempArray = new int[end - begin + 1]; int i = 0; //point to empArray while (pa <= middle && pb <= end) //无论那个子数组到尾部了都退出 { if (A[pa] >= A[pb]) //控制从小到大，还是从大到小 { *(tempArray + i) = A[pa++]; i++; } else { *(tempArray + i) = A[pb++]; i++; } } if (pa > middle) { for (int j = pb; j <= end; j++) { *(tempArray + i) = A[pb++]; i++; } } else if (pb > end) { for (int j = pa; j <= middle; j++) { *(tempArray + i) = A[pa++]; i++; } } for (int j = begin; j <= end; j++) { A[j] = *(tempArray + j - begin); } delete [] tempArray; } /************************************************* Function: MergeSort Description:对数组进行从小到大归并排序 Input: B:ElementType类型的数组 begin:需要归并排序的数组的开始序号 end:需要归并排序的数组的结束序号 *************************************************/ void MergeSort(int B[], int begin, int end) { if (end == begin) { return; } else if ((end - begin) == 1) { if (B[begin] < B[end]) //控制排序升降 { //交换两数 int temp = B[begin]; B[begin] = B[end]; B[end] = temp; } } else { int middle = (begin + end) / 2; MergeSort(B, begin, middle); MergeSort(B, middle + 1, end); Merge(B, begin, middle, end); } }