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: 第一个3对来自于序列[1,2]，[1,4]，[1,6]，
[7,2]，[7,4]，[11,2]，[7,6]，[11,4]，
[11,6]

方法1（简单）

找到所有的对并存储它们的和。此步骤的时间复杂度为O(n1*n2)，其中n1和n2是输入数组的大小。
然后按总和对对进行排序。此步骤的时间复杂度为O(n1n2 * log (n1n2))

总时间复杂度: O(n1n2 * log (n1n2))

方法2（有效）：

我们从最小的配对开始一次找到k个最小的和。其思想是跟踪已经针对每个元素arr1 [i1]考虑的arr2 []的所有元素，以便在迭代中我们只考虑下一个元素。为此，我们使用一个索引数组index2 []来跟踪另一个数组中的下一个元素的索引。它仅意味着在每个迭代中，第一个数组中的哪个元素应与第二个数组的元素相加。我们在每个迭代中增加索引数组中的值以形成下一个最小值对。

// C++ program to prints first k pairs with least sum from two
// arrays.
#include<bits/stdc++.h>
 
using namespace std;
 
// Function to find k pairs with least sum such
// that one element of a pair is from arr1[] and
// other element is from arr2[]
void kSmallestPair(int arr1[], int n1, int arr2[],
                                   int n2, int k)
{
    if (k > n1*n2)
    {
        cout << "k pairs don't exist";
        return ;
    }
 
    // Stores current index in arr2[] for
    // every element of arr1[]. Initially
    // all values are considered 0.
    // Here current index is the index before
    // which all elements are considered as
    // part of output.
    int index2[n1];
    memset(index2, 0, sizeof(index2));
 
    while (k > 0)
    {
        // Initialize current pair sum as infinite
        int min_sum = INT_MAX;
        int min_index = 0;
 
        // To pick next pair, traverse for all elements
        // of arr1[], for every element, find corresponding
        // current element in arr2[] and pick minimum of
        // all formed pairs.
        for (int i1 = 0; i1 < n1; i1++)
        {
            // Check if current element of arr1[] plus
            // element of array2 to be used gives minimum
            // sum
            if (index2[i1] < n2 &&
                arr1[i1] + arr2[index2[i1]] < min_sum)
            {
                // Update index that gives minimum
                min_index = i1;
 
                // update minimum sum
                min_sum = arr1[i1] + arr2[index2[i1]];
            }
        }
 
        cout << "(" << arr1[min_index] << ", "
             << arr2[index2[min_index]] << ") ";
 
        index2[min_index]++;
 
        k--;
    }
}
 
// Driver code
int main()
{
    int arr1[] = {1, 3, 11};
    int n1 = sizeof(arr1) / sizeof(arr1[0]);
 
    int arr2[] = {2, 4, 8};
    int n2 = sizeof(arr2) / sizeof(arr2[0]);
 
    int k = 4;
    kSmallestPair( arr1, n1, arr2, n2, k);
 
    return 0;
}

输出

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

时间复杂度： O(k*n1)，其中n1表示给定数组的大小。

辅助空间： O(n1)，其中n1表示给定数组的大小。

方法3： 使用排序，最小堆，映射

不要通过所有可能的和组合来进行蛮力搜索，应该找到一种方式来限制我们的搜索空间以寻找可能的候选和组合。

对数组A和数组B进行排序。
创建一个min heap，即在C++中使用priority_queue将和组合以及组成和的数组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] + B [j + 1]，i，j + 1）插入min heap中，但确保索引对，即（i +1，j）和（i，j +1）在min heap中不存在。在C++中可以使用set来检查这一点。
回到第4步，重复K次。

// C++程序：打印
// 两个数组中的最小和的前k个元素对。
 
#include <bits/stdc++.h>
using namespace std;
 
// 找到k个最小元素对的函数
// 一个元素来自arr1[]，
// 另一个元素来自arr2[]
void kSmallestPair(vector<int> A, vector<int> B, int K)
{
    sort(A.begin(), A.end());
    sort(B.begin(), B.end());
 
    int n = A.size();
 
    // 包含元组的小根堆，格式为
    // (sum, (i, j))，i和j是数组A
    // 和数组B中将和表示出来元素的下标。
 
    priority_queue<pair<int, pair<int, int> >,
                   vector<pair<int, pair<int, int> > >,
                   greater<pair<int, pair<int, int> > > >
        pq;
 
    // my_set用于存储元组(i, j)的下标
    // 我们使用my_set来确保
    // 小根堆里不存在重复下标。
 
    set<pair<int, int> > my_set;
 
    // 用最小的和组合初始化堆，即(A[0] + B[0])
    // 并将下标(0,0)与和一起推入堆中。
 
    pq.push(make_pair(A[0] + B[0], make_pair(0, 0)));
 
    my_set.insert(make_pair(0, 0));
 
    // 迭代至K
    int flag=1;
    for (int count = 0; count < K && flag; count++) {
 
        // 元组格式为(sum, i, j)。
        pair<int, pair<int, int> > temp = pq.top();
        pq.pop();
 
        int i = temp.second.first;
        int j = temp.second.second;
 
        cout << "(" << A[i] << ", " << B[j] << ")"
             << endl; // 提取和最小的元素对，
                      // 一个元素来自arr1，
                      // 另一个来自arr2。
 
        // 检查i+1是否在我们第一个数组A的范围内
        flag=0;
        if (i + 1 < A.size()) {
            int sum = A[i + 1] + B[j];
            // 将 (A[i+1]+B[j], (i+1, j))插入到堆中
            // 仅在(i+1, j)这个下标对不在堆中时才插入。
 
            pair<int, int> temp1 = make_pair(i + 1, j);
 
            // 只有当这个元组 (i+1, j) 不在集合中时，才插入。
 
            if (my_set.find(temp1) == my_set.end()) {
                pq.push(make_pair(sum, temp1));
                my_set.insert(temp1);
            }
          flag=1;
        }
        // 检查j+1是否在我们第二个数组B的范围内
        if (j + 1 < B.size()) {
            // 将 (A[i]+B[j+1], (i, j+1))插入到堆中。
 
            int sum = A[i] + B[j + 1];
            pair<int, int> temp1 = make_pair(i, j + 1);
 
            // 仅在(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<int> A = { 1 };
    vector<int> B = { 2, 4, 5, 9 };
    int K = 3;
    kSmallestPair(A, B, K);
    return 0;
}