3a995a4ccc27a1e6e8681d46f7e2c20a
(难度Hard)Problem 23. Merge k Sorted Lists(K个链表归并)

链接

https://leetcode.com/problems/merge-k-sorted-lists/

难度等级

Hard

题干

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

题意

合并K个有序链表

样例

Input:
[
  1->4->5,
  1->3->4,
  2->6
]
Output: 1->1->2->3->4->4->5->6

题解

解法一 暴力

第一反应应该就是暴力大法,这道题暴力解法比较明显。不管几个链表,总之目的是一个:把这些元素归并成一个有序的链表。

既然如此,我们可以简单粗暴地把所有的元素集合在一起,然后再进行排序。

复杂度就两个,一个是遍历的复杂度一个是排序的复杂度。很明显遍历的复杂度是$O(n)$排序的复杂度是$O(nlogn)$。所以整体的复杂度就是$O(nlogn)$

伪代码:

def mergeK(lists):
    arr = []
    # 读取所有元素
    for list in lists:
        h = list.head
        while h != null:
            arr.append(h->value)
            h = h->next
    h = new ListNode(0)
    # 排序
    sorted(arr)
    for i in arr:
        h->next = new ListNode(i)
        h = h->next
    return h->next

解法二 按位枚举

解法一的弊端相信大家也能看得出来,那就是无视了这k个链表是有序的这个信息。

我们把这个信息用起来,完全可以进行优化。

比较容易想到就是,我们可以仿照两个链表归并的方式,一位一位地归并。每次遍历这k个链表的首元素,挑选出最小的那个,放入结果链表当中。被选中的链表往后移动一位,循环往复,直到所有链表都为空为止。

伪代码:

def mergeK(lists, k):
    ret = new ListNode(0)
    pnt = ret->next
    while lists !全部为空:
        h = null
        mini = MAXINT
        for list in lists:
            if list is Null:
                continue
            if list->val < mini:
                mini = list->val
                h = list
        pnt = new ListNode(mini)
        h = h->next
        pnt = pnt->next
    return ret->next

我们分析一下复杂度,最极端的情况下我们每次获取元素都需要遍历k个链表,那么复杂度就是$O(kn)$。

top Created with Sketch.