C++程序在两个数组中找到k对最小元素之和

在编程领域，我们经常需要在两个数组中查找特定规则的数对。本文将介绍如何使用C++编程在两个数组中找到k对最小元素之和。

算法思路

我们可以使用一个最小堆来实现查找。初始化时，我们将第一个数组的前k个元素与第二个数组的前k个元素相加，并将结果加入最小堆中。然后，我们逐个遍历第一个数组的剩余元素，并相加第二个数组的所有元素，将结果与最小堆的堆顶元素进行比较。如果比堆顶元素小，就将结果加入堆中，并弹出堆顶元素。这样，最终我们将得到k对最小元素之和。

C++代码实现

下面是我们的C++实现代码：

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

class Solution {
public:
    vector<pair<int, int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
        // 建立一个最小堆
        auto cmp = [](pair<int, int> a, pair<int, int> b){
            return a.first + a.second > b.first + b.second;
        };
        priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> Q(cmp);
        // 将第一个数组的前k个元素与第二个数组的前k个元素相加并加入堆中
        for(int i=0; i<min((int)nums1.size(), k); ++i) {
            for(int j=0; j<min((int)nums2.size(), k); ++j) {
                if(Q.size() < k) Q.push(make_pair(nums1[i], nums2[j]));
                else {
                    auto temp = Q.top();
                    if(nums1[i]+nums2[j]<temp.first+temp.second) {
                        Q.pop();
                        Q.push(make_pair(nums1[i], nums2[j]));
                    }
                }
            }
        }
        // 将结果从最小堆中取出
        vector<pair<int, int>> res;
        while(!Q.empty()) {
            res.push_back(Q.top());
            Q.pop();
        }
        // 结果翻转后返回
        reverse(res.begin(), res.end());
        return res;
    }
};

int main() {
    vector<int> nums1 = {1,7,11};
    vector<int> nums2 = {2,4,6};
    Solution s;
    vector<pair<int, int>> res = s.kSmallestPairs(nums1, nums2, 3);
    for(auto p : res) {
        cout << "[" << p.first << ", " << p.second << "]" << endl;
    }
    return 0;
}

上面的代码包含了一个Solution类，其中kSmallestPairs方法是我们解决这个问题的核心方法。这个方法接受两个数组和一个整数k，返回一个包含k对最小元素之和的数组。我们可以通过类似下面的语法来调用这个方法：

Solution s;
vector<pair<int, int>> res = s.kSmallestPairs(nums1, nums2, k);

代码解释

在我们的代码中，我们首先定义了一个pair类型的vector，用于保存k对最小元素之和。然后，我们建立了一个最小堆（使用STL中的priority_queue来管理堆），用于查找k对最小元素之和。

在最小堆的初始化中，我们定义了一个lambda函数，用于比较两个pair类型的元素。这个函数返回的结果是a.first + a.second > b.first + b.second，这个函数的意义是：当a的第一个元素加上第二个元素的值小于b的第一个元素加上第二个元素的值时，函数返回true。这个lambda函数就是我们最小堆的比较函数。

在方法的最开始，我们遍历了第一个数组的前k个元素和第二个数组的前k个元素，计算它们的和，并将结果加入最小堆中。之后，我们遍历第一个数组余下的元素，并相加第二个数组的所有值，将结果与堆顶元素进行比较。如果结果比堆顶元素小，则将结果加入堆中，并弹出堆顶元素。最终，我们从堆中取出结果并返回，这就是所谓的k对最小元素之和。