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

给定两个以 非递减顺序排列 的整数数组 nums1 和 nums2 , 以及一个整数 k 。定义一对值 (u,v)其中第一个元素来自 nums1第二个元素来自 nums2 。请找到和最小的 k 个数对 (u1,v1), (u2,v2) … (uk,vk) 。示例 1:输入: nums1 [1,7,11], nums2 [2,4,6], k 3输出: [[1,2],[1,4],[1,6]]解释: 返回序列中的前 3 对数[1,2],[1,4],[1,6],[7,2],[7,4],[11,2],[7,6],[11,4],[11,6]示例 2:输入: nums1 [1,1,2], nums2 [1,2,3], k 2输出: [[1,1],[1,1]]解释: 返回序列中的前 2 对数[1,1],[1,1],[1,2],[2,1],[1,2],[2,2],[1,3],[1,3],[2,3]提示:1 nums1.length, nums2.length 105^55-109^99 nums1[i], nums2[i] 109^99nums1 和 nums2 均为 升序排列1 k 104^44k nums1.length * nums2.length对于示例1我们可以把所有可能的和看成一个矩阵其中每行都是非递减的我们可以将其当作合并K个有序链表那样每行的最小元素都放到堆里来处理classSolution{public:vectorvectorintkSmallestPairs(vectorintnums1,vectorintnums2,intk){vectortupleint,int,inth(nums1.size());for(inti0;inums1.size();i){h[i]{nums1[i]nums2[0],i,0};}make_heap(h.begin(),h.end(),greater());vectorvectorintans;ans.reserve(k);for(inti0;ik;i){auto[_,idx1,idx2]h[0];ans.push_back({nums1[idx1],nums2[idx2]});pop_heap(h.begin(),h.end(),greater());if(idx2nums2.size()-1){h.back(){nums1[idx1]nums2[idx21],idx1,idx21};push_heap(h.begin(),h.end(),greater());}else{h.pop_back();}}returnans;}};如果nums1的长度为n则此算法时间复杂度为O(n klogn)空间复杂度为O(n)。