python - 合并排序数组算法

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

所有归功于> https://discuss.leetcode.com/topic/33609/10-line-python-solution-with-priority-queue