各アレイAiが{1..i}のランダムサブセットであるA1..Anをマージする

Question

A1にラベル付けされたn個のアレイを効率的にマージする方法を見つけようとしています。

各アレイAiは{1..i}のサブセットです。たとえば、A3は{1}、{3}、{1,3}とすることができます。各配列がソートされていることに注意してください。

たとえば、n = 8, A1={}, A2={2}, A3={2,3}, A4={1,4}, A5=A6=A7={}, A8={6}の場合、それらのすべてをマージすると{1,2,3,4,6}となります。

私はすべての配列にO（n^2）個の要素があり、作成できるのでO（n^2）、よりも速くの方法を見つけようとしています。サイズnの配列を作成し、各要素をバケットに入れようとします。

Answer 1

合計n個のアイテムを含むソートされた整数配列kがある場合は、O（k）の余分なスペースを使用してそれらをO（n log k）時間でマージできます。これはどのように行われたのですか：

まず、配列と現在のインデックスを配列に保持するタイプpqitemを作成します。そして

class pqitem 
    int[] A; 
    int i; 

、pqitemインスタンスを保持する優先度キュー（MIN-ヒープ）を作成例：。比較関数はA[i]を比較する必要があるため、ヒープ内の項目は、現在の項目が最小の配列がルートになるように配置されます。

各アレイに対して、配列を保持するpqitemインスタンスを作成します。 iフィールドを0に初期化します。優先キューに挿入します。

今度はヒープから一番低いアイテムを削除し、現在の値を出力してiを増やし、i < A.lengthの場合はヒープにアイテムを戻します。つまり、

myHeap = new heap() 
for each array 
    item = new pqitem(array, 0) 
    myHeap.Add(item) 

while (myHeap.count > 0) 
    item = myHeap.pop() 
    output item.A[item.i] // output or add to new array, etc. 
    ++item.i 
    if (item.i < item.A.length) 
     myHeap.Add(item) 

あなたの場合、重複を防止したいと考えています。したがって、マージループをわずかに変更して、最後のアイテム出力を追跡し、重複アイテムの出力を防止します。

// keep track of the previous item 
prev = -1 // Initialize to a value that won't appear in the lists 
while (myHeap.count > 0) 
    item = myHeap.pop() 
    // skip duplicates 
    if (item.A[item.i] != prev) 
     output item.A[item.i] // output or add to new array, etc. 
     prev = item.A[item.i] 
    ++item.i 
    if (item.i < item.A.length) 
     myHeap.Add(item) 

Answer 2

あなたはi番目の配列、インデックスiとインデックスkのk番目のアイテムを保持するコンテナを必要としています。

public class Node { 
    int item, arrIndx, itemIndx; 
    public Node(int a, int b, int c) { 
     this.item = a; 
     this.arrIndx = b; 
     this.itemIndx = c; 
    } 
} 

はNodeを含むことのminheap（昇順でその要素をソートし続けるプライオリティキュー）を使用します。

まず、配列ごとに、最初の要素をminHeapにプッシュします。 minHeapが最初にn要素をソートしている。

minHeapから前面要素を1つずつポップして、配列のすべての項目の中で最も小さい要素を出力配列に配置します。 i番目の配列のk番目の要素をポップするときは、i番目の配列のk + 1要素をキューに入れます。このようにして、現在の最小要素のすぐ下の要素を押しています。

すべての配列要素がminHeapからプッシュおよびポップされるまで、このプロセスを続行します。

サンプルJavaスニペットは次のようになります。

public List<Integer> mergekSortedArrays(int[][] arrays) { 

    List<Integer> result = new ArrayList<Integer>(); 

    if (arrays == null || arrays.length == 0) { 
     return result; 
    } 

    PriorityQueue<Node> minHeap = new PriorityQueue<Node>(arrays.length, 
     new Comparator<Node>() { 
      public int compare(Node lhs, Node rhs) { 
       return lhs.item - rhs.item; 
      } 
     } 
    ); 

    // O(n log n) 
    for (int i = 0; i < arrays.length; i++) { 
     if (arrays[i].length > 0) { 
      minHeap.offer(new Node(arrays[i][0], i, 0)); 
     } 
    } 

    Node node; 

    // O((N - n)log n) 
    while (!minHeap.isEmpty()) { 
     node = minHeap.poll(); 
     result.add(node.item); 
     if (node.itemIndx + 1 < arrays[node.arrIndx].length) { 
      minHeap.offer(new Node(arrays[node.arrIndx][node.itemIndx + 1], node.arrIndx, node.itemIndx + 1)); 
     } 
    } 

    return result; 

} 

時間複雑度はnは、アレイの数であり、Nは、これらの配列のすべての要素の数であるO(N log n)です。