Steward

分享是一種喜悅、更是一種幸福

程式語言 - LeetCode - CPP - 373. Find K Pairs with Smallest Sums

---

參考資訊：
https://www.cnblogs.com/grandyang/p/5653127.html

題目：


解答：

class Solution {
public:
    vector<vector<int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {
        priority_queue<pair<int, vector<int>>> pq;

        for (int n1 : nums1) {
            for (int n2 : nums2) {
                int sum = n1 + n2;

                if (pq.size() < k) {
                    pq.push({sum, { n1, n2 }});
                }
                else if (sum < pq.top().first) {
                    pq.pop();
                    pq.push({sum, { n1, n2 }});
                }
                else {
                    break;
                }
            }
        }

        vector<vector<int>> ans;
        while (!pq.empty()) {
            ans.push_back(pq.top().second);
            pq.pop();
        }

        return ans;
    }
};