[数据结构与算法]leetcode ---优先队列题

剑指 Offer II 061. 和最小的 k 个数对? ?力扣

class Solution {
public:

struct cmp {
    bool operator()(const pair<int,int>& n,const pair<int,int>& m) {
        return n.first + n.second > m.first + m.second;
    }
};

   priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> qu;
    vector<vector<int>> res;
    vector<vector<int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
        int size1 = nums1.size();
        int size2 = nums2.size();

        for (int i = 0; i < size1; ++i) {
            for (int j = 0; j < size2; ++j) {
                pair<int, int> tmp;
                tmp.first = nums1[i];
                tmp.second = nums2[j];
                qu.push(tmp);
            }
        }

        if (k > qu.size()) {
            k = qu.size();
        }
        while(k) {
            pair<int, int> tmp = qu.top();;
            vector<int> vec;
            vec.push_back(tmp.first);
            vec.push_back(tmp.second);
            res.push_back(vec);
            qu.pop();
            k--;
        }
        return res;


    }
};

也可以用暴力解法

class Solution {
public:
   /* bool cmp(vector<int> a, vector<int> b) {
        return (a[0] + a[1]) <= (b[0] + b[1]);
    } */
    vector<vector<int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
        vector<vector<int>> con;
        vector<vector<int>> res;
        int size1 = nums1.size();
        int size2 = nums2.size();
        
        vector<int> tmp;
        for (int i = 0; i < size1; ++i) {
            for (int j = 0; j < size2; ++j) {
                tmp.push_back(nums1[i]);
                tmp.push_back(nums2[j]);
                con.push_back(tmp);
                tmp.clear();
            }
        }
        std::sort(con.begin(),con.end(),[](const auto& pa,const auto& pb){
            return pa[0]+pa[1]< pb[0]+pb[1];
        });
        if (k > con.size()) {
            return con;
        }
        for (int i = 0; i < k; ++i) {
            res.push_back(con[i]);
        }
        return res;
        
    }