ソートされた配列アルゴリズムをマージする

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

これは一般的なプログラミングのインタビューの質問です。私がこれまで見た最もエレガントな解決策には、次ました：>https://discuss.leetcode.com/topic/33609/10-line-python-solution-with-priority-queue

Answer 2

へ

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 

すべてのクレジットこれはやや高速です - およそ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)) 

EDIT：私はあなたが理論的な意味（インタビューの質問のようなもの）を考えているのかどうかはこれが最善の答えではないと思っています - &のビルドインのpython関数を悪用する良い例：P

Answer 3

リーフコードには非常によく似た質問があります。https://leetcode.com/problems/merge-k-sorted-lists/description/ k個のソート済みリストをマージし、時間の複雑さはO（Nlogk）です。ここでNはk個のリストの総数です。

アルゴリズムの主な方法は、サイズkの最小ヒープを作成し、それに要素を追加することです。 leetcodeのウェブサイトの詳細な説明があったので、それを見てみることをお勧めしました。

Answer 4

Python独自の標準ライブラリは、私がO（kn log n）と仮定するヒープベースの解heapq.mergeを提供しています。私はあなたがO（kn log n）よりもうまくいくかどうかは疑問です。

sourceのheapq.mergeは、見たい場合はそれほど長くはありません。