c++ solution using priority_queue


  • 0
    H
    class Solution {
    public:
        vector<pair<int, int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
            vector<pair<int, int>> ans;
            if(nums1.empty() || nums2.empty() || k <= 0) return ans;
            auto cmp = [&nums1, &nums2](pair<int, int> a, pair<int, int> b) {
                return nums1[a.first] + nums2[a.second] > nums1[b.first] + nums2[b.second];
            };
            priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> pq(cmp);
            //pq.emplace(0, 0);
            pq.push({0, 0});
            while(k -- && !pq.empty()) {
                auto idx1 = pq.top().first, idx2 = pq.top().second;
                pq.pop();
                //ans.emplace_back(nums1[idx1], nums2[idx2]);
                ans.push_back({nums1[idx1], nums2[idx2]});
                if(idx1 < nums1.size() - 1)
                    //pq.emplace(idx1 + 1, idx2);
                    pq.push({idx1 + 1, idx2});
                if(idx1 == 0 && idx2 < nums2.size() - 1)
                    //pq.emplace(idx1, idx2 + 1);
                    pq.push({idx1, idx2 + 1});
            }
            
            return ans;
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.