欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

合并 K 个排序链表

程序员文章站 2022-07-27 20:58:59
合并 K 个排序链表leetcode 38合并 k 个排序链表,返回合并后的排序链表。请分析和描述算法的复杂度。示例:输入:[ 1->4->5, 1->3->4, 2->6]输出: 1->1->2->3->4->4->5->6分治法使用和归并排序一样的分治算法。每两个链表进行合并,逐层返回。既使用了分治法,也使用了递归。# 分治法def mergeKLists(self, lists: List[L...
合并 K 个排序链表

leetcode 38

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

示例:

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

使用和归并排序一样的分治算法。

每两个链表进行合并,逐层返回。既使用了分治法,也使用了递归。

# 分治法
def mergeKLists(self, lists: List[ListNode]) -> ListNode:
    return self.merge(lists, 0, len(lists) - 1)
 
def merge(self, lists, left, right):
    if left == right:
        return lists[left]
    if left < right:
        mid = left + right >> 1
        return self.mergeTwoList(self.merge(lists, left, mid), self.merge(lists, mid+1, right))
 
def mergeTwoList(self, l1, l2):
    if not l1:
        return l2
    if not l2:
        return l1
    if l1.val < l2.val:
        l1.next = self.mergeTwoList(l1.next, l2)
        return l1
    l2.next = self.mergeTwoList(l1, l2.next)
    return l2

方法一

第一种考虑是将所有元素放置到最小堆里,堆会自动调整顺序。

考虑优先队列中的元素不超过 nn 个,那么每次插入和删除的时间代价为 O(logn)O(\log n),所以整体时间复杂度是 O(nlogn)O(n \log n)nn 代表元素的总和。

空间复杂度是 O(n)O(n)

def mergeKLists(self, lists: List[ListNode]) -> ListNode:
    if not lists:
        return
    queue = []
    cur = dummy = ListNode(0)
    for node in lists:
        while node:
            heapq.heappush(queue, (node.val, node))  # 需要 ListNode 构造加上 _lt_
            node = node.next
    while queue:
        _, cur.next = heapq.heappop(queue)
        cur = cur.next
    return dummy.next

我们设想在堆里放入:node.val, node,前者用于比较大小,后者直接用于链表的组装。

但是会出现:TypeError: '<' not supported between instances of 'ListNode' and 'ListNode'错误。
原因是:堆元素可以为元组进行排序。元组在 heapq 里比较的机制是从元组首位 0 开始,即遇到相同,就比较元组下一位,比如 (1,2), (1,3),前者比后者小。
这题刚好 node 值有重复的,同时 ListNode 无法被比较,所以可以解释编译器为什么报错。

解决方法是在类 ListNode 里面添加比较方法

class ListNode:
    def __init__(self, x):
        self.val = x
        self.next = None
 
    def __lt__(self, other):
        return self.val < other.val

__lt__ 是定义对象比较的 < 操作,当然你定义为 > 也没毛病。两个写一个就行。

    def __gt__(self, other):
        return self.val > other.val

不足之处:
就是相当于取出全部元素进行由大到小排序,然后进行链表的拼接,而排序的时间复杂度是 O(nlogn)O(n \log n),很明显这种方法并没有利用堆降低时间复杂度。

方法二:真正堆的使用

我们维护一个大小为 kk 的堆,堆由每个链表的首元素组成,每次堆弹出一个元素,就由该链表的下个结点进入。
如图所示:
合并 K 个排序链表

# 假定已经定义了 ListNode 的比较方法
def mergeKLists(self, lists: List[ListNode]) -> ListNode:
    if not lists:
        return
    queue = []
    cur = dummy = ListNode(0)
    for node in lists:
        if node:
            heapq.heappush(queue, node)  # 同样需要 ListNode 构造加上 _lt_
 
    while queue:
        head = heapq.heappop(queue)
        cur.next = head
        cur = cur.next
        if head.next:
            heapq.heappush(queue, head.next)
    return dummy.next

若是没有定义结点的比较方法,我们可以将堆里面存入结点的值和链表所在的索引号

def mergeKLists(self, lists: List[ListNode]) -> ListNode:
    if not lists:
        return
    queue = []
    cur = dummy = ListNode(0)
    for i, node in enumerate(lists):
        if node:
            heapq.heappush(queue, (node.val, i))
  
    while queue:
        val, idx = heapq.heappop(queue)
        cur.next = ListNode(val)
        cur = cur.next
        if lists[idx].next:
            heapq.heappush(queue, (lists[idx].next.val, idx))
            lists[idx] = lists[idx].next  # lists[idx] 相当于指针,这点很有意思。
    return dummy.next

时间复杂度为 O(nlogk)O(n \log k),空间复杂度是 O(k)O(k)

参考

四种解法+多图演示 23. 合并K个排序链表
合并 K 个排序链表
python c++ 优先队列(最小堆) O(n*logk)
合并K个排序链表

本文地址:https://blog.csdn.net/weixin_43932942/article/details/107101700