力扣373.查找和最小的K对数字
用小根堆找每次最小的(根据非递减)
- 由于处理(i,j)的两个儿子(i-1,j)和(i,j-1)时 如果将父亲入队 会重复
- 所以可以令当前取出(i,j-1)时才让父亲入队
- 取(i-1,j)时仅计算答案(加入ans)
- 预处理将所有(i,0)入队 否则之后入不了
class Solution { public: vector<vector<int>> kSmallestPairs(vector<int>& nums1, vector<int>& nums2, int k) { vector<vector<int>> ans; //三元组存元素 priority_queue<tuple<int,int,int>> q; int n = nums1.size(), m = nums2.size(); for(int i=0;i<min(n,k);i++) //数值改为负数 原本大根堆 -> 小根堆 q.emplace(-nums1[i] - nums2[0] ,i ,0); while(!q.empty() && ans.size()<k) { //取出i,j两下标的语法 auto [_,i,j] = q.top(); q.pop(); ans.push_back({nums1[i],nums2[j]}); //但凡j+1还在范围都可以入队 if(j + 1 < m) q.emplace(-nums1[i] - nums2[j + 1],i ,j+1); } return ans; } };