K路归并(堆实现)

本题出处为LeetCode 23题,难度为困难。

问题

合并 k 个排序链表,返回合并后的排序链表。请分析和描述算法的复杂度。

示例:

输入:
[
  1->4->5,
  1->3->4,
  2->6
]
输出: 1->1->2->3->4->4->5->6

解法

  1. 链表已经有序,可以读取每个链表中的第一个元素,一共K个元素,选出其中的最小值,将该元素加入到新的链表中并从原来的链表中删除。一共执行N次,最终构建出新的有序链表。
  2. 如果每次从K个元素中选出最小值,单次的时间复杂度为O(N),总的时间复杂度为O(KN),有优化空间。可以将K个元素放入堆中。每次从堆顶取出一个元素,因为堆序关系,每次取出的元素是堆中的最小值。然后继续将该元素的下一个元素加入堆中,每次加入的时间复杂度是O(logK),一共执行N次,所以复杂度降为O(NlogK)。
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def mergeKLists(self, lists: List[ListNode]) -> ListNode:
        dummy_head = ListNode(0)
        ptr = dummy_head
        heap = []
        for i, node in enumerate(lists):
            if node:
                heapq.heappush(heap, (node.val, i))
                lists[i] = node.next

        while heap:
            val, i = heapq.heappop(heap)
            ptr.next = ListNode(val)
            ptr = ptr.next
            node = lists[i]
            if node:
                lists[i] = node.next
                heapq.heappush(heap, (node.val, i))
        return dummy_head.next

复杂度分析

设N为数组中元素的总数,K为数组的个数。

  • 时间复杂度 O(NlogK)
    • 每次heappush复杂度 O(logK),总共执行N次。
  • 空间复杂度 O(N)
    • 创建新的链表需要分配N个内存空间,创建堆需要分配K个内存空间,K<=N,最终为 O(N)。

《K路归并(堆实现)》上有2条评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注