Tìm K cặp có tổng nhỏ nhất trong C++

Cho 2 mảng đã sắp xếp nums1, nums2 và số k. Tìm k cặp (u,v) có tổng nhỏ nhất (u từ nums1, v từ nums2).

Ví dụ: nums1 = [1,7,11], nums2 = [2,4,6], k = 3 → [(1,2),(1,4),(1,6)].

Thuật toán giải quyết (Min-heap + Chỉ số)

1. Khởi tạo min-heap chứa (sum, i, j) với i = 0..n-1, j = 0 (cặp với phần tử đầu tiên của nums2).
2. Lặp k lần (hoặc heap rỗng):
   • Pop cặp nhỏ nhất (sum, i, j), thêm (nums1[i], nums2[j]) vào kết quả.
   • Nếu j+1 < m → push (nums1[i] + nums2[j+1], i, j+1).

Ví dụ minh họa (C++)

#include <bits/stdc++.h>
using namespace std;

struct Data {
    int sum, i, j;
    Data(int s, int i, int j) : sum(s), i(i), j(j) {}
    bool operator>(const Data& other) const { return sum > other.sum; }
};

class Solution {
public:
    vector<vector<int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
        int n = nums1.size(), m = nums2.size();
        if (!n || !m) return {};
        priority_queue<Data, vector<Data>, greater<Data>> pq;
        for (int i = 0; i < n; i++) pq.emplace(nums1[i] + nums2[0], i, 0);
        vector<vector<int>> ret;
        while (!pq.empty() && k--) {
            auto cur = pq.top(); pq.pop();
            ret.push_back({nums1[cur.i], nums2[cur.j]});
            if (cur.j + 1 < m) pq.emplace(nums1[cur.i] + nums2[cur.j+1], cur.i, cur.j+1);
        }
        return ret;
    }
};

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

Đầu vào

[1,7,11] [2,4,6] 3

Đầu ra

[[1,2],[1,4],[1,6]]