leetcode分类刷题：队列（Queue）（三、优先队列用于归并排序）

1、当TopK问题出现在多个有序序列中时，就要用到归并排序的思想了
2、将优先队列初始化为添加多个有序序列的首元素的形式，再循环K次优先队列的出队和出队元素对应序列下个元素的入队，就能得到TopK的元素了
3、这些题目好像没有TopK 大用小顶堆，TopK 小用大顶堆反着来的经验了，得顺着来了：TopK 大用大顶堆，TopK 小用小顶堆

23. 合并 K 个升序链表

1、优先队列用于归并排序的经典题目：给定的有序序列为升序链表，要将所有升序链表合并成一个升序链表
2、该题直接用小顶堆实现归并排序，初始化时将所有头节点（每个有序序列的最小值）入堆，再依次弹出优先队列进行节点之间的连接；如果要直接将ListNode入堆，需要重写<，即__lt__()函数，使得节点之间能进行比较

from typing import Optional, List
import heapq
'''
23. 合并 K 个升序链表
给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
示例 1:输入：lists = [[1,4,5],[1,3,4],[2,6]]输出：[1,1,2,3,4,4,5,6]解释：链表数组如下：[1->4->5,1->3->4,2->6]将它们合并到一个有序链表中得到。1->1->2->3->4->4->5->6
思路1、将所有链表元素全部加入优先队列（小顶堆），再依次弹出优先队列重新建立节点赋值
思路2、将链表按照（头节点值，索引，头节点）形式加入优先队列（小顶堆），再依次弹出优先队列进行节点连接——不理解为什么去掉元组里的索引就会出错
思路3、自定义节点的比较方式，直接将节点加入优先队列（小顶堆），再依次弹出优先队列进行节点连接——这叫归并？
'''class ListNode:def __init__(self, val=0, next=None):self.val = valself.next = nextclass Solution:def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]:# # 思路1、将所有链表元素全部加入优先队列（小顶堆），再依次弹出优先队列重新建立节点赋值# # 情况1、数组为空# if len(lists) == None:#     return None# # 情况2、将数组中所有链表添加到小顶堆# que = []# for head in lists:#     if head != None:#         cur = head#         while cur != None:#             heapq.heappush(que, cur.val)#             cur = cur.next# # 继续将小顶堆的元素弹出构建为新的链表# dummyHead = ListNode(-1)# cur = dummyHead# while len(que) > 0:#     cur.next = ListNode(heapq.heappop(que))#     cur = cur.next# return dummyHead.next# # 思路2、将链表按照（头节点值，索引，头节点）形式加入优先队列（小顶堆），再依次弹出优先队列进行节点连接# # 情况1、数组为空# if len(lists) == None:#     return None# # 情况2、将链表按照（头节点值，索引，头节点）形式加入优先队列（小顶堆）# que = []# for i in range(len(lists)):#     if lists[i] != None:#         heapq.heappush(que, (lists[i].val, i, lists[i]))# # 将小顶堆的节点弹出进行连接# dummyHead = ListNode(-1)# cur = dummyHead# while len(que) > 0:#     _, i, head = heapq.heappop(que)#     if head.next != None:#         heapq.heappush(que, (head.next.val, i, head.next))#     cur.next = head#     cur = cur.next# return dummyHead.next# 思路3、自定义节点的比较方式，直接将节点加入优先队列（小顶堆），再依次弹出优先队列进行节点连接class Comparer:def __init__(self, node: Optional[ListNode]):self.node = nodedef __lt__(self, other):return self.node.val < other.node.val# 情况1、数组为空if len(lists) == None:return None# 情况2、将节点加入优先队列（小顶堆）que = []for head in lists:if head != None:heapq.heappush(que, Comparer(head))# 将小顶堆的节点弹出进行连接dummyHead = ListNode(-1)cur = dummyHeadwhile len(que) > 0:head = heapq.heappop(que).nodeif head.next != None:heapq.heappush(que, Comparer(head.next))cur.next = headcur = cur.nextreturn dummyHead.next

接下来的3道题目都是在leetcode分类刷题：二分查找（Binary Search）（四、基于值域的数组/矩阵类型）总结过的，当时就觉得值域二分法+双指针的思路也太复杂了，果然用归并排序的思想就要容易多了

378. 有序矩阵中第 K 小的元素

1、优先队列用于归并排序的经典题目：没有显式给定多个有序序列，需要将矩阵的每一行看作是一个个有序序列
2、该题目一开始我按照TopK 大用小顶堆，TopK 小用大顶堆反着来先用的大顶堆，并保持元素总数为K，提交后发现会超时！
3、直接用小顶堆实现归并排序，初始化时将所有矩阵第一列（每个有序序列的最小值）入堆，再循环K次小顶堆的出堆和出堆元素对应序列下个元素的入堆，循环结束就能得到第K小的元素了
4、这里题目的关键还是在于多个有序序列，循环K次小顶堆的出堆总是能保证依次出队的是最小、次小等依此类推，循环K次小顶堆的入堆也总是能保证所有有序序列各自的最小值都在堆中（除非该有序序列被访问完毕）

from typing import List
import heapq
'''
378. 有序矩阵中第 K 小的元素
题目描述：给你一个n x n矩阵matrix ，其中每行和每列元素均按升序排序，找到矩阵中第 k 小的元素。
请注意，它是 排序后 的第 k 小元素，而不是第 k 个 不同 的元素。
你必须找到一个内存复杂度优于O(n2) 的解决方案。
示例 1:输入：matrix = [[1,5,9],[10,11,13],[12,13,15]], k = 8输出：13解释：矩阵中的元素为 [1,5,9,10,11,12,13,13,15]，第 8 小元素是 13
题眼：Top K
思路1、优先队列（大顶堆）：保持堆内元素总数为k，那么堆顶元素即为第k个最小元素
思路2、归并排序：采用优先队列（小顶堆），归并k次得到第k小的数，类似“23. 合并 K 个升序链表”
'''class Solution:def kthSmallest(self, matrix: List[List[int]], k: int) -> int:# # 思路1、优先队列（大顶堆）：保持堆内元素总数为k，那么堆顶元素即为第k个最小元素# n = len(matrix)# que = []# for i in range(n):#     for j in range(n):#         heapq.heappush(que, -matrix[i][j])  # 添加相反数：因为python默认维护小顶堆#         if len(que) > k:#             heapq.heappop(que)# return -que[0]# 思路2、归并排序：采用优先队列（小顶堆），归并k次得到第k小的数，类似“23. 合并 K 个升序链表”n = len(matrix)que = []# 初始化优先队列（小顶堆）for i in range(n):heapq.heappush(que, (matrix[i][0], i, 0))  # 将每一行的最小值加入：堆顶元素为第一小的元素for _ in range(k - 1):_, i, j = heapq.heappop(que)if j + 1 <= n - 1:  # 每次归并都要加入出堆序列中的最小值，保证所有排序序列各自的最小值都在堆中，直到序列为空heapq.heappush(que, (matrix[i][j + 1], i, j + 1))return heapq.heappop(que)[0]if __name__ == '__main__':obj = Solution()while True:try:in_line = input().strip().split('=')matrix = []for row in in_line[1].strip()[1: -4].split(']')[:-1]:matrix.append([int(n) for n in row.split('[')[1].split(',')])k = int(in_line[2])# print(matrix, k)print(obj.kthSmallest(matrix, k))except EOFError:break

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

1、优先队列用于归并排序的经典题目：没有显式给定多个有序序列，可以模拟成“378. 有序矩阵中第 K 小的元素”的矩阵形式，将nums1当作矩阵的行，nums2当作矩阵的列，再把矩阵的每一行看作是一个个有序序列
2、该题目按照值域二分+双指针需要分别添加小于小于pairSum的数对和等于pairSum的数对，非常容易出错，换成归并排序的解法就没那么繁杂了
3、这道题我也一开始我按照TopK 大用小顶堆，TopK 小用大顶堆反着来先用的大顶堆，并保持元素总数为K，提交后发现也会超时！
4、直接用小顶堆实现归并排序，初始化时将所有nums1的元素+nums[0]（每个有序序列的最小值）入堆，再循环K次小顶堆的出堆和出堆元素对应序列下个元素的入堆，循环结束就能得到第K小的元素了
5、这道题目还有个细节，可能K会大于所有数对的数量，即升序返回数对就可以了，是一种不用排序的情况
6、这里题目的关键还是在于多个有序序列，循环K次小顶堆的出堆总是能保证依次出队的是最小、次小等依此类推，循环K次小顶堆的入堆也总是能保证所有有序序列各自的最小值都在堆中（除非该有序序列被访问完毕）

from typing import List
import heapq
'''
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]
题眼：Top K
思路1、优先队列（大顶堆）：保持元素总数为k个，最终k个元素为最小的k个：会超时
思路2、归并排序：利用上两个序列是递增数组的条件，模拟成“378. 有序矩阵中第 K 小的元素”的矩阵形式，将nums1当作矩阵的行，nums2当作矩阵的列，建立优先
队列（小顶堆），归并k次得到前最k小的数
'''class Solution:def kSmallestPairs(self, nums1: List[int], nums2: List[int], k: int) -> List[List[int]]:# # 思路1、优先队列（大顶堆）：保持元素总数为k个，最终k个元素为最小的k个：会超时# que = []# for n1 in nums1:#     for n2 in nums2:#         heapq.heappush(que, (-(n1 + n2), n1, n2))  # 大顶堆：添加相反数，因为Python默认维护小顶堆#         if len(que) > k:#             heapq.heappop(que)# result = [[0] for _ in range(len(que))]# for i in range(len(result) - 1, -1, -1):#     _, n1, n2 = heapq.heappop(que)#     result[i] = [n1, n2]# return result# 思路2、归并排序：利用上两个序列是递增数组的条件，模拟成“378. 有序矩阵中第 K 小的元素”的矩阵形式，将nums1当作矩阵的行，nums2当作矩阵的列，# 建立优先队列（小顶堆），归并k次得到前最k小的数result = []# 情况1、所有数对都要被返回：也可以把k=min(k,len(nums1)*len(nums2))合并到情况2去写if len(nums1) * len(nums2) <= k:for n1 in nums1:for n2 in nums2:result.append([n1, n2])return result# 情况2、归并k次得到前最k小的数que = []# 初始化优先队列（小顶堆）for i in range(len(nums1)):heapq.heappush(que, (nums1[i] + nums2[0], i, 0))# 归并k次得到前最k小的数for _ in range(k):_, i, j = heapq.heappop(que)result.append([nums1[i], nums2[j]])if j + 1 <= len(nums2) - 1:heapq.heappush(que, (nums1[i] + nums2[j + 1], i, j + 1))return resultif __name__ == '__main__':obj = Solution()while True:try:in_line = input().strip().split('=')nums1 = [int(n) for n in in_line[1].strip().split('[')[1].split(']')[0].split(',')]nums2 = [int(n) for n in in_line[2].strip().split('[')[1].split(']')[0].split(',')]k = int(in_line[3])# print(nums1, nums2, k)print(obj.kSmallestPairs(nums1, nums2, k))except EOFError:break

719. 找出第 K 小的数对距离

1、优先队列用于归并排序的经典题目：没有显式给定多个有序序列，可以模拟成以索引0~len(nums)-2为距离起点的len(nums)-1个有序序列，每个序列的元素总数为len(nums)-1、len(nums)-2…1
2、这道题我也一开始我按照TopK 大用小顶堆，TopK 小用大顶堆反着来先用的大顶堆，并保持元素总数为K，提交后发现也会超时！
3、直接用小顶堆实现归并排序，初始化时将所有以索引0~len(nums)-2为距离起点的距离（每个有序序列的最小值）入堆，再循环K次小顶堆的出堆和出堆元素对应序列下个元素的入堆，循环结束就能得到第K小的元素了，最终提交后还是超时了，主要是这道题目有个比较长的测试用例，没办法，看来还是只能用值域二分+双指针了

import heapq
from typing import List
'''
719. 找出第 K 小的数对距离
题目描述：数对 (a,b) 由整数 a 和 b 组成，其数对距离定义为 a 和 b 的绝对差值。
给你一个整数数组 nums 和一个整数 k ，数对由 nums[i] 和 nums[j] 组成且满足 0 <= i < j < nums.length 。
返回 所有数对距离中 第 k 小的数对距离。
示例 1:输入：nums = [1,3,1], k = 1输出：0解释：数对和对应的距离如下：(1,3) -> 2(1,1) -> 0(3,1) -> 2距离第 1 小的数对是 (1,1) ，距离为 0 。
题眼：TopK
思路1、优先队列（大顶堆）：保持堆内元素个数为K，则堆顶元素为第K小的：会超时
思路2、归并排序：优先队列（小顶堆），类似“373. 查找和最小的 K 对数字”，本题在排序后会存在len(nums)-1个升序序列，然后进行k次归并排序得到前最k小的数
'''class Solution:def smallestDistancePair(self, nums: List[int], k: int) -> int:# # 思路1、优先队列（大顶堆）：保持堆内元素个数为K，则堆顶元素为第K小的：会超时# que = []# for i in range(len(nums)):#     for j in range(i + 1, len(nums)):#         heapq.heappush(que, -abs(nums[i] - nums[j]))  # 大顶堆：添加相反数，因为Python默认维护小顶堆#         if len(que) > k:#             heapq.heappop(que)# return -que[0]# 思路2、归并排序：优先队列（小顶堆），类似“373. 查找和最小的 K 对数字”，本题在排序后会存在len(nums)-1个升序序列，然后进行k次归并排序# 得到前最k小的数nums.sort()que = []for i in range(len(nums) - 1):  # 初始化 优先队列（小顶堆）heapq.heappush(que, (abs(nums[i] - nums[i + 1]), i, i + 1))result = 0# 归并k次得到前最k小的数for _ in range(k):result, i, j = heapq.heappop(que)if j + 1 <= len(nums) - 1:heapq.heappush(que, (abs(nums[i] - nums[j + 1]), i, j + 1))return resultif __name__ == "__main__":obj = Solution()while True:try:in_line = input().strip().split('=')nums = [int(n) for n in in_line[1].split('[')[1].split(']')[0].split(',')]k = int(in_line[2])print(obj.smallestDistancePair(nums, k))except EOFError:break