力扣373.查找和最小的K对数字

力扣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;
        }
    };