|
这个题纠结了两个多月，一直没有找到很好的解决方法，现在终于能够找到一种很满意的方法了。
题目：有两个大小都是k的数组A,B，它们元素的按非递减有序排列，找出这样的k个最小的(ai + bj) ,其中 0<= i,j < k,要求算法的时间复杂度和空间复杂度尽量低。
想到的最简单的方法就是开辟一个k*k的二维数组，然后计算所有的(ai + bj)， 然后在其中找到最小的k个(ai + bj)，但是这样的时间复杂度和空间复杂度都很高O（k^2）。
那么接下来就讲一种最新的方法吧：该方法类似于胜者树或者败者树，就想多路归并排序一样。首先，“臆造”这样一个二维数组，它有k行k列，第（i,j）位置的元素是ai + bj的和。然后定义如下的结构体：
typedef struct node{
int row;
int col;
int data;;
}node;
分配k个这样的存储空间给bin，把我们臆造的二维数组的第一列放在这个数组中，并标示每个元素来自的行列，行标示在A中的位置，列标示在B中的位置。所得到的这样一个一位数组并不一定是按元素data大小有序的。但是由于两个数组A,B都是有序的，所以可以肯定第（0,0）位置的元素是第一小的。找到第一个小的元素之后怎么做呢，显然是要用下一个ai
+ bj来填补这个空白，我所选的策略是保持i不变，然后让j值增1，也就是ai + b（j+1）的值。填补之后，我们又重新得到了一个bin数组，但是它的所有元组并不是按照索引值递增而元素值data也递增的。所以要找一个排序方法，但是并不是要求所有元组都有序，只要取出bin中最小的那个就好，所以选择建立一个小根堆，算法导论有有一篇证明可以在O（k）的时间内建立堆， 然而调整堆只需要O（lgk）的时间。每次求得一个最小元素之后，也就是取得堆顶元素之后，就要用bin[0]所在行的下一个元素代替它然后调整堆，这样经过k此操作，就能得到最小的k个组合值。这个概念可以理解为多路并行方法。时间复杂度是O(k*lgk),
空间复杂度是O(k)。下面给出代码：
代码可以处理有重复元素的情况，如果有什么不妥的地方，希望大家给与指点。
#include<iostream>
using namespace std;
typedef struct node{
int row;
int col;
int data;
}Node, *PNode;
void swap(PNode &a, PNode &b) {
PNode temp = a;
a = b;
b = temp;
}
void adjust_min_heap(PNode *bin, int i, int k) {
int left = 2 * i + 1;
int right = 2 * i + 2;
int min_index;
if(left < k && bin[left]->data < bin[i]->data) {
min_index = left;
} else {
min_index = i;
}
if(right < k && bin[right]->data < bin[min_index]->data) {
min_index = right;
}
if(min_index != i) {
swap(bin[i], bin[min_index]);
adjust_min_heap(bin, min_index, k);
}
}
void build_min_heap(PNode *bin, int k) {
for(int i = k / 2; i >= 0; i--) {
adjust_min_heap(bin, i, k);
}
}
int *get_k_th_minimum(int *a, int *b, int k) {
PNode *bin = (PNode*)malloc(sizeof(PNode) * k);
int *result = (int*)malloc(sizeof(int) * k);
memset(result, 0, sizeof(int) * k);
int i;
int count = 0;
for(i = 0; i < k; i++) {
bin[i] = (Node*)malloc(sizeof(Node));
bin[i]->row = i;
bin[i]->col = 0;
bin[i]->data = a[i] + b[0];
}
build_min_heap(bin, k);
while(count < k) {
result[count++] = bin[0]->data;
bin[0]->col += 1;
bin[0]->data = a[bin[0]->row] + b[bin[0]->col];
adjust_min_heap(bin, 0, k);
}
for(i = 0; i < k; i++) {
free(bin[i]);
}
free(bin);
return result;
}
void main() {
int a[] = {1, 3, 6};
int b[] = {4, 5, 6};
int k = 3;
int *p = get_k_th_minimum(a, b, k);
for(int i = 0; i < k; i++) {
cout << p[i] << " ";
}
free(p);
getchar();
}
扩展思考：如果要找最小的2k个组合呢，这个程序代码需要哪里做修改呢。
| 
转播
