C++ 找到两个数组中和最小的k对

给定两个升序整数数组arr1[]和arr2[]，以及一个整数k。确定具有最小和的k对，其中一个元素属于arr1[]，另一个元素属于arr2[]。

示例：

Input :  arr1[] = {1, 7, 11}
         arr2[] = {2, 4, 6}
         k = 3
Output : [1, 2],
         [1, 4],
         [1, 6]
Explanation: The first three pairs from the sequence [1, 2], [1, 4], [1, 6], [7, 2], [7, 4], [11, 2], [7, 6], [11, 4], [11, 6] are returned.

方法1（简单）

找到所有的配对并记录它们的和。这一步的时间复杂度为O(n1 * n2)，其中n1和n2是输入数组的大小。

然后按照和对配对进行排序。这一步的时间复杂度为O(n1 * n2 * log (n1 * n2))。

O(n1 * n2 * log (n1 * n2)) 是总体 时间复杂度 。
O(n1*n2) 是 辅助空间。

方法2（强大）

从最小和的配对开始，我们逐个发现k个最小和的配对。目标是跟踪每个数组array1[i1]已经被调查的array2[]元素，这样在每次迭代中我们只需要考虑下一个元素。我们利用索引数组indexno2[]来维护另一个数组中后续元素的索引，以实现这个目的。它只是表示在每次迭代中应该将第二个数组的哪个元素添加到第一个数组的元素中。对于形成下一个最小值配对的元素，我们增加索引数组中的值。

C++的实现：

#include

using namespace std;

void kSmallestP(int array1[], int n1, int array2[],
                                int n2, int k)
{
    if (k > n1*n2)
    {
        cout << "k pairs don't exist";
        return ;
    }
    int indexno2[n1];
    memset(indexno2, 0, sizeof(indexno2));

    while (k > 0)
    {
        int minimum_sum = INT_MAX;
        int minimum_index = 0;
        for (int i1 = 0; i1 < n1; i1++)
        {

            if (indexno2[i1] < n2 &&
                array1[i1] + array2[indexno2[i1]] < minimum_sum)
            {
                minimum_index = i1;
                minimum_sum = array1[i1] + array2[indexno2[i1]];
            }
        }

        cout << "(" << array1[minimum_index] << ", "
            << array2[indexno2[minimum_index]] << ") ";

        indexno2[minimum_index]++;

        k--;
    }
}
int main()
{
    int array1[] = {1, 3, 11};
    int n1 = sizeof(array1) / sizeof(array1[0]);

    int array2[] = {2, 4, 8};
    int n2 = sizeof(array2) / sizeof(array2[0]);

    int k = 4;
    kSmallestP( array1, n1, array2, n2, k);

    return 0;
}

输出：

(1, 2) (1, 4) (3, 2) (3, 4)

时间复杂度 将会是 O(k*n1).
辅助空间 将会是 O(n1).

方法3：排序、最小堆和映射

与其通过暴力搜索所有可能的求和组合，我们应该开发一种策略，将搜索空间缩小到可能的候选求和组合。

在C++中，创建一个最小堆，即priority_queue，用于保存求和组合以及数组A和B中组成求和的分量的索引。求和用于对堆进行排序。
用来自数组A和B的条目的索引以及最小可能求和组合(A[0] + B[0]) (0, 0) 初始化堆。在最小堆内，元组将是(A[0] + B[0], 0, 0)。堆按照第一个值排序，即两个项的求和。
弹出堆，获取当前最小求和以及构成求和的元素索引。允许元组为(sum, i, j)。

将(A[i + 1] + B[j], i + 1, j)和(A[i + 1], i, j + 1)插入最小堆，但要确保索引对(i + 1, j)和(i, j + 1)不已经存在。在C++中，我们可以使用set来进行测试。
返回至步骤4重复K次。

C++实现：

#include 
using namespace std;

void kSmallestP(vector A, vector B, int K)
{

    int n = A.size();

    priority_queue >,
                vector > >,
                greater > > >
        pq;

    set > my_set;

    pq.push(make_pair(A[0] + B[0], make_pair(0, 0)));

    my_set.insert(make_pair(0, 0));

    int flag = 1;
    for (int count = 0; count < K && flag; count++) {

        pair > temp = pq.top();
        pq.pop();

        int i = temp.second.first;
        int j = temp.second.second;

        cout << "(" << A[i] << ", " << B[j] << ")"
            << endl; 
        flag = 0;
        if (i + 1 < A.size()) {
            int sum = A[i + 1] + B[j];

            pair temp1 = make_pair(i + 1, j);

            if (my_set.find(temp1) == my_set.end()) {
                pq.push(make_pair(sum, temp1));
                my_set.insert(temp1);
            }
            flag = 1;
        }

        if (j + 1 < B.size()) {
            int sum = A[i] + B[j + 1];
            pair temp1 = make_pair(i, j + 1);


            if (my_set.find(temp1) == my_set.end()) {
                pq.push(make_pair(sum, temp1));
                my_set.insert(temp1);
            }
            flag = 1;
        }
    }
}

int main()
{
    vector A = { 1 };
    vector B = { 2, 4, 5, 9 };
    int K = 8;
    kSmallestP(A, B, K);
    return 0;
}

输出：