373. 查找和最小的K对数字 - 力扣（LeetCode）

优先级队列求topK的典型题目，

先来一个暴力的排序法：

class Solution {
public:vector<vector<int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) {vector<vector<int>> sums;for(int i=0;i<nums1.size();++i){for(int j=0;j<nums2.size();++j){sums.push_back({nums1[i],nums2[j]});//将所有的可能都加进去}}sort(sums.begin(), sums.end(), [](vector<int>& l, vector<int>& r){return (l[0]+l[1] < r[0]+r[1]);});if(k > sums.size()) return sums;vector<vector<int>> res(sums.begin(), sums.begin()+k);return res;}
};

使用优先级队列求topK:

class Solution{
public:struct cmp{bool operator() (const pair<int, int> &a, const pair<int, int> &b) {return a.first + a.second < b.first + b.second; }};vector<vector<int>> kSmallestPairs(vector<int> &nums1, vector<int> &nums2, int k){int n = nums1.size(), m = nums2.size();vector<vector<int>> res; //输出结果if (n == 0 || m == 0) return res;priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> q;//这儿用的是大顶堆for(int i = 0; i < n; ++i){//两层循环遍历元素for(int j = 0; j < m; ++j){if(q.size() < k)	q.push({nums1[i], nums2[j]});else if(nums1[i]+nums2[j] < q.top().first + q.top().second){//比此时队首的最大值要小，那就取而代之q.pop();q.push({nums1[i], nums2[j]});}}}while(!q.empty()){//把元素倒出来res.push_back({q.top().first, q.top().second});q.pop();}reverse(res.begin(), res.end());return res;}
};