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 = val
        self.next = next


class 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 = node

            def __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 = dummyHead
        while len(que) > 0:
            head = heapq.heappop(que).node
            if head.next != None:
                heapq.heappush(que, Comparer(head.next))
            cur.next = head
            cur = cur.next
        return dummyHead.next
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96

接下来的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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

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 result


if __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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69

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 result


if __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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57