C++分治法查找两数之和为给定数的数对
时间: 2023-05-31 12:02:28 浏览: 59
算法描述:
使用分治法查找两数之和为给定数的数对,首先将数组从中间分成两个部分,然后递归地在左右两个部分中查找满足条件的数对,最后再将左右两个部分中的数对进行合并。
算法实现:
```c
#include <stdio.h>
void merge(int arr[], int l, int mid, int r) {
int i = l, j = mid + 1, k = 0;
int temp[r - l + 1];
while (i <= mid && j <= r) {
if (arr[i] + arr[j] == 10) {
printf("(%d, %d)\n", arr[i], arr[j]);
i++;
j++;
} else if (arr[i] + arr[j] < 10) {
i++;
} else {
j++;
}
}
}
void mergeSort(int arr[], int l, int r) {
if (l < r) {
int mid = (l + r) / 2;
mergeSort(arr, l, mid);
mergeSort(arr, mid + 1, r);
merge(arr, l, mid, r);
}
}
int main() {
int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
int size = sizeof(arr) / sizeof(arr[0]);
mergeSort(arr, 0, size - 1);
return 0;
}
```
算法分析:
时间复杂度为 O(nlogn),空间复杂度为 O(n)。