归并排序阵列算法

Question

我必须创建合并排序数组的算法。以下是我所做的：

import sys

lists = [[1,2,3], 
         [-100, 70], 
         [23, 50]]
pivot = [0] * len(lists) # [0, 0, 0]
finalSorted = []


for _ in range(sum(len(x) for x in lists)): # quantity of items in 2D array 
    smallest = sys.maxint
    index_of_smallest = -1      
    for indx, list in enumerate(lists):
        if pivot[indx] < len(list):
            current = list[pivot[indx]]
            if current <= smallest:
                smallest = current
                index_of_smallest = indx

    finalSorted.append(smallest)
    pivot[index_of_smallest] = pivot[index_of_smallest]+1

print(finalSorted) #[-100, 1, 2, 3, 23, 50, 70]

问题：

1. 这是最好的方法吗？
2. 算法复杂度是kn^2吗？其中'k‘是平均数组长度，n是数组数量。
3. 它是否只适用于k比n大得多的情况？这样的k和n有哪一种快速方式成为更好的解决方案？

Answer 1

这是个很受欢迎的节目面试问题。到目前为止，我看到的最优雅的解决方案如下：

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

全信用to> https://discuss.leetcode.com/topic/33609/10-line-python-solution-with-priority-queue

Answer 2

这有点快--大约是我实验的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

Answer 3

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

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