首页 > 其他分享 >优先队列-多路归并系列题解

优先队列-多路归并系列题解

时间:2022-08-27 10:22:06浏览次数:69  
标签:11 归并 队列 题解 List int res nums1 nums2

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]
示例 3:
输入: nums1 = [1,2], nums2 = [3], k = 3
输出: [1,3],[2,3]
解释: 也可能序列中所有的数对都被返回:[1,3],[2,3]
提示:
1 <= nums1.length, nums2.length <= 105
-109 <= nums1[i], nums2[i] <= 109
nums1 和 nums2 均为升序排列
1 <= k <= 1000

问题求解

可以将原问题转为多路归并问题:可以看作是以(i,0)开头的多个列表进行归并。

class Solution:
    def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:
        n, m = len(nums1), len(nums2)
        res = []

        h = []
        for i in range(n):
            heappush(h, (nums1[i] + nums2[0], i, 0))
        
        while len(res) < k and h:
            s, i, j = heappop(h)
            res.append([nums1[i], nums2[j]])
            if j + 1 < m: heappush(h, (nums1[i] + nums2[j + 1], i, j + 1))
        
        return res

标签:11,归并,队列,题解,List,int,res,nums1,nums2
From: https://www.cnblogs.com/hyserendipity/p/16629906.html

相关文章

  • asyncio队列 asyncio.Queue()
    importasyncio#如果maxsize小于等于零,则队列尺寸是无限的。#如果是大于0的整数,则当队列达到maxsize时,awaitput()将阻塞至某个元素被get()取出Q=async......
  • 优先队列-2386. 找出数组的第 K 大和
    问题描述给你一个整数数组nums和一个正整数k。你可以选择数组的任一子序列并且对其全部元素求和。数组的第k大和定义为:可以获得的第k个最大子序列和(子序......
  • 【题解】CF1007D Ants
    传送门题意:有\(m\)对链,每对链要选择一条,使得选择的链两两不交,求一组方案。题解:一眼看上去就是一个2-sat,考虑一种暴力的做法,枚举每一条边,覆盖这条边的链两两连边。......
  • 题解 UVA10791
    前言:数学符号约定:\(p\):任意一个质数\(n\)或\(m\):任意一个正整数\(a_i\):唯一分解时质数的指数\(A\):集合若无特殊说明,本篇题解的数学符号将会严格按照上......
  • 20220823 模拟赛题解
    T1文件压缩DecriptionlinkSolution可以根据\(S'\)和\(p\)求出第一个字符,然后把\(S'\)sort一遍后得到字符串\(T\),那么我们就可以求出每一个字符的前驱和后继,所......
  • LeetCode 232. 用栈实现队列
    思路:用两个栈实现队列pop操作,若out栈为空则先将in中元素push进out,再pop出out中元素peek操作,直接调用pop,在将pop出元素push进outclassMyQueue{public:stack<int......
  • LeetCode 链表的中间结点算法题解 All In One
    LeetCode链表的中间结点算法题解AllInOnejs/ts实现重排链表链表的中间结点原理图解//快慢指针functionmiddleNode(head:ListNode|null):ListNode|n......
  • 归并排序
    packagecom.inforcreation;importjava.util.Arrays;/***归并排序**归并排序(Mergesort)是建立在归并操作上的一种有效的排序算法,*归并排序对序列的元素进......
  • k8s问题解决
    问题1:问题描述:k8s中Terminating状态pod不能删除[root@master~]#kubectlgetpods-nmsNAMEREADYSTATUSRESTARTSAGEportal-78......
  • Unable to create an object of type 'DbContext'问题解决,网上搜来的没一个对的。
    用了很久的EFCore了,第一次遇到这个问题,觉得很奇怪,baidu了一下,都是要提供设计时工厂的答案。很明显这个做法是有问题的,都是DI的年代了,你的DbContext又不是动态生产了一堆......