YeungYeah 的乱写地

Merge k Sorted Lists

 Posts  

Problem

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

Example:

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

Solution

分析

问题是对于K个有序链表的排序与合并，所以第一时间就能想到归并排序。在归并排序中，我们可将两个有序数组通过常数时间的比较，线性时间一次遍历即可。此处为k个列表，则有k个数的比较，比较的复杂度就不为常数时间。由此马上想到了第一个暴力的方法。

1. k个归并

思路与归并排序一致，只是将比较从两个数变为k个数，每一轮比较k个列表的第一个元素（最小值），找出最小值并更新该链表指针。因而单轮比较的复杂度变为与k相关的线性时间，设数字个数总和为n个（下同），则时间复杂度为$O(kn)$。代码如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

class Solution:
    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """
        ret = ans = ListNode(-1)
        lists = list(filter(lambda x:x,lists))#去除特例k=0
        while lists:
            point,mini=0,lists[0].val
            for i,l in enumerate(lists):
                if l.val<mini:
                    point,mini=i,l.val
            ans.next = ListNode(mini)
            ans = ans.next
            if lists[point].next:lists[point]=lists[point].next
            else: del lists[point]
        return ret.next

该种方法简单直接粗暴，在leetcode上也能通过，但是执行用时很大，处在后9%的位置，不值得推荐

2. 用堆归并

在方法1中，每一轮寻找k个列表中的最小值均需要线性时间复杂度，且每一轮中除开最小值外，其余元素均会被重复访问，浪费了此前的遍历过程，于是我们可以引入最小堆，来存储每个链表中的最小值，每一轮弹出最小值后只需动态更新最小堆即可。初始建立最小堆的时间复杂度为$O(klog(k))$，每获取并添加一个最小的元素，并更新最小堆所需的时间复杂度为$O(log(k))$，所以总的时间复杂度为$O(nlog(k))$（因为n>k恒成立

 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

class Solution:
    class cmp_node:
        def __init__(self, node):
            self._node = node
            self.val = node.val

        def __lt__(self, other):
            return self.val < other.val

    def mergeKLists(self, lists):
        """
        :type lists: List[ListNode]
        :rtype: ListNode
        """
        list_heap = []
        for i in range(len(lists)):
            if lists[i]:
                list_heap.append(self.cmp_node(lists[i]))
        if not list_heap:
            return None

        import heapq
        heapq.heapify(list_heap)
        head = walk = heapq.heappop(list_heap)._node
        if walk.next:
            heapq.heappush(list_heap, self.cmp_node(walk.next))
        while list_heap:
            walk.next = heapq.heappop(list_heap)._node
            walk = walk.next
            if walk.next:
                heapq.heappush(list_heap, self.cmp_node(walk.next))
        return head

这里使用了python标准库中自带的堆库，其中可以对一个list建堆只要list中的元素可以比较（这通过建立新类型并实现__lt__函数实现。

该方法为方法1的优化版本，执行时间大幅减少，并且思路较为简单，因为python提供堆的标准库，实现也比较简单，在熟悉标准库的情况下，值得推荐。可是对我这种并不知道基本数据结构的标准库的人来说，要我手写一个堆很是麻烦，因此我也用不了

3. 两两归并

思路跟归并排序一样，甚至相比与方法1，更加接近归并排序。这种方法使用递归的思路，每次将所有链表分成两部分，每一部分均调用原函数再次合并，然后将两部分的链表进行合并，当两部分的链表出现只有两个时，可直接套用归并排序中的合并。所以该方法的时间复杂度为$O(nlog(k))$，其中log(k)为递归调用次数。

将复杂度而言，该方法与方法2使用堆的方法复杂度相近，但该方法无须用到数据结构堆，使用了递归的思想，更容易实现。

4. 合并排序

提交之后看别人执行用时少的方法，发现排在最前面的方法居然是一种很暴力的方法：遍历所有链表合成一个数组，然后进行排序，再重新生成一个链表。按照时间复杂度来分析，遍历所有元素生成数组需要时间n，排序需要nlogn，总共需要$O(nlogn)$时间复杂度，按理来说，这个时间复杂度是要比上面的方法二方法三都要慢的，但实际上，这反而是最快的，看了一下讨论区，说的是python中排序算法的实现底层使用了c语言来实现的，所以用时比实际的其它python操作要快得多。但感觉这个方法还是不太好，因为这种方法还完全忽略了题目中链表这一性质（虽然也没怎么用到）

相关文章：