跳转至

373 查找和最小的 K 对数字

可转换为合并k条有序链表: - 第一条链表: nums1[0]作为数对的第一个元素,剩余nums2的元素作为数对的第二个元素 - 第二条链表: nums1[1]作为数对的第一个元素,剩余nums2的元素作为数对的第二个元素 - 以此类推,总共nums1.size()条链表 - 接着合并这些链表即可

class Solution {
public:
    struct State{
        int u;
        int v;
        int pv;
    };
    struct cmp{
        bool operator() (const State& s1, const State& s2) const{
            return (s1.u + s1.v) > (s2.u + s2.v);
        }
    };
    vector<vector<int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
        priority_queue<State, vector<State>, cmp> heap;
        for(int i = 0; i < nums1.size(); i++){
            heap.push(State(nums1[i], nums2[0], 0));
        }
        vector<vector<int>> res;
        while(k > 0 && !heap.empty()){
            State s = heap.top();
            heap.pop();
            res.push_back({s.u,s.v});
            if(s.pv + 1 < nums2.size()){
                heap.push(State(s.u, nums2[s.pv + 1], s.pv + 1));
            }
            k--;
        }
        return res;
    }
};