合并排序数组算法

这是一个流行的节目采访问题。到目前为止,我看到的最优雅的解决方案是:

from Queue import PriorityQueue

def mergeKLists(lists):
    dummy = ListNode(None)
    curr = dummy
    q = PriorityQueue()
    for node in lists:
        if node: q.put((node.val,node))
    while q.qsize()>0:
        curr.next = q.get()[1]
        curr=curr.next
        if curr.next: q.put((curr.next.val, curr.next))
    return dummy.next

https://discuss.leetcode.com/topic/33609/10-line-python-solution-with-priority-queue

这要快一些——大约是我实验的1.5倍:

from itertools import izip_longest

final = []
second = lambda x: x[1]
while any(lists):
    idx, _ = min(enumerate(next(izip_longest(*lists, fillvalue=sys.maxint))), key=second)
    final.append(lists[idx].pop(0))

编辑:我想如果你更多地从理论的角度思考这个问题(例如,作为一个面试问题),这不是最好的答案——这是一个使用&但是滥用内置python函数:P

关于leetcode有一个非常类似的问题: https://leetcode.com/problems/merge-k-sorted-lists/description/ 它合并k个排序列表,时间复杂度为O(Nlogk),其中N是k个列表的总数。

该算法的主要方法是构建一个大小为k的最小堆,并向其中添加元素。因为leetcode网站上有详细的解释,我建议你可以看看。

Python自己的标准库提供了基于堆的解决方案 heapq.merge 我假设它是O(kn log n)。我怀疑你能做得比O(kn log n)更好。

source 属于 heapq。合并 不是太长,如果你想看看的话。