6

私はこの質問がされたことを知っており、最小ヒープを使用した非常に優れたエレガントなソリューションがあります。

私の質問は、マージソートのマージ機能を使用してこれを行う方法です。

並べ替えられた配列の配列が既にあります。つまり、O(nlog K) 時間でそれらすべてを 1 つの配列にマージできるはずですよね?

これを行う方法がわかりません！

私が持っていると言う

[ [5,6]、[3,4]、[1,2]、[0] ]

ステップ 1: [ [3,4,5,6], [0,1,2] ]

Step2: [ [0,1,2,3,4,5,6] ]

これを行う簡単な方法はありますか？O(nlog K) はマージソートで理論的に達成可能ですか?

4

5 に答える 5

6

複雑さが O(n log k) であると言うとき、n は k 個の配列すべての要素の総数、つまり最終的にマージされた配列の要素の数を意味すると仮定することに注意してください。

たとえば、それぞれ n 個の要素を含む k 個の配列をマージする場合、最終的な配列の要素の総数は nk になります。したがって、複雑さは O(nk log k) になります。

于 2014-12-09T06:34:18.627 に答える
2

配列をマージするにはさまざまな方法があります。そのタスクを N*Log(K) 時間で達成するには、ヒープと呼ばれる構造を使用できます (優先キューを実装するのに適した構造です)。利用可能な実装を選択しない場合は、既にそれを持っていると思います: http://en.wikipedia.org/wiki/Heap_(data_structure) 次に、次のように行うことができます:

1.  We have A[1..K] array of arrays to sort, Head[1..K] - current pointer for every array and Count[1..K] - number of items for every array.
2.  We have Heap of pairs (Value: int; NumberOfArray: int) - empty at start.
3.  We put to the heap first item of every array - initialization phase.
4.  Then we organize cycle:
5.  Get pair (Value, NumberOfArray) from the heap. 
6.  Value is next value to output.
7.  NumberOfArray – is number of array where we need to take next item (if any) and place to the heap.
8.  If heap is not empty, then repeat from step 5

したがって、すべてのアイテムについて、K 個のアイテムから構築されたヒープのみを最大として操作します。あなたが尋ねたように、N*Log(K) の複雑さがあることを意味します。

于 2013-09-24T14:48:51.807 に答える
1

Pythonで実装しました。主なアイデアはマージソートに似ています。リストには k 個の配列があります。関数 mainMerageK では、リスト (k) を左 (k/2) と右 (k/2) に分割するだけです。したがって、パーティションの合計数は log(k) です。関数のマージに関しては、実行時間が O(n) であることは簡単にわかります。最後に、O(n log k) を取得します。ちなみに、これも最小ヒープで実装できます。リンクがあります: Merging K-Sorted Lists using Priority Queue

def mainMergeK(*lists):
    # implemented by k-way partition
    k = len(lists)
    if k > 1:
        mid = int(k / 2)
        B = mainMergeK(*lists[0: mid])
        C = mainMergeK(*lists[mid:])
        A = merge(B, C)
        print B, ' + ', C, ' = ', A
        return A
    return lists[0]

def merge(B, C):
    A = []
    p = len(B)
    q = len(C)
    i = 0
    j = 0
    while i < p and j < q:
        if B[i] <= C[j]:
            A.append(B[i])
            i += 1
        else:
            A.append(C[j])
            j += 1
    if i == p:
        for c in C[j:]:
            A.append(c)
    else:
        for b in B[i:]:
            A.append(b)
    return A

if __name__ == '__main__':
    x = mainMergeK([1, 3, 5], [2, 4, 6], [7, 8, 10], [9])
    print x

出力は以下のようになります:

[1, 3, 5]  +  [2, 4, 6]  =  [1, 2, 3, 4, 5, 6]
[7, 8, 10]  +  [9]  =  [7, 8, 9, 10]
[1, 2, 3, 4, 5, 6]  +  [7, 8, 9, 10]  =  [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
于 2016-05-12T14:00:57.773 に答える