Fusionner n tableaux A1..An avec chaque Array Ai étant un sous-ensemble aléatoire de {1..i}

Question

J'essaie de trouver un moyen de fusionner n tableaux étiquetés A1 à An efficacement.

Chaque tableau Ai est un sous-ensemble de {1..i}. Par exemple, A3 pourrait être {1} ou {3} ou {1,3}. Notez que chaque tableau est trié. Par exemple pour n = 8, A1={}, A2={2}, A3={2,3}, A4={1,4}, A5=A6=A7={}, A8={6}, la fusion de tous donnerait {1,2,3,4,6}. J'essaie de trouver un moyen de faire cela plus vite que O (n^2), ce qui est évident puisqu'il y a O (n^2) éléments totaux dans tous les tableaux et nous pouvons créer un tableau de taille n et essayez de mettre chaque élément dans un seau.

Answer 1

Si vous avez k tableaux triés d'entiers contenant un total combiné de n éléments, vous pouvez les fusionner en temps O (n log k), en utilisant un espace supplémentaire O (k). Voici comment cela est fait:

D'abord, créez un type appelé pqitem, qui contient un tableau et l'index actuel dans le tableau. Par exemple: pour tenir pqitem instances

class pqitem 
    int[] A; 
    int i; 

Ensuite, créez une file d'attente prioritaire (min-tas). La fonction de comparaison doit comparer A[i], de sorte que les éléments dans le tas sont disposés de sorte que le tableau avec le plus petit élément actuel soit à la racine.

Pour chacune des baies, créez une instance pqitem pour contenir la baie. Initialisez le champ i à 0. Insérez dans la file d'attente de priorité.

Maintenant, supprimez continuellement l'élément le plus bas du tas, affichez la valeur actuelle, augmentez i et ajoutez l'élément au tas si i < A.length. C'est-à-dire:

Dans votre cas, vous voulez éviter les doublons. Vous modifiez donc légèrement la boucle de fusion pour conserver la sortie du dernier élément et empêcher la sortie d'éléments en double.

// 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

Vous avez besoin d'un conteneur qui contiendra l'élément k e du tableau i e, l'indice et l'indice ik.

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

Utilisez une minHeap (File d'attente prioritaire qui maintiennent triée son élément dans l'ordre croissant) pour contenir le Node.

Au début de chaque tableau, placez son premier élément dans le minHeap. Comment minHeap détient les premiers éléments triés n.

Maintenant, placez l'élément frontal du minHeap un par un qui est le plus petit parmi tous les éléments de tableaux et placez-le dans le tableau de sortie. Pendant le lancement de tout élément k du tableau i, placez l'élément k + 1 ème élément du tableau i dans la file d'attente. De cette façon, nous nous assurons, nous poussons le plus petit élément immédiat du plus petit élément actuel.

Continuez ce processus jusqu'à ce que tous les éléments de tableaux soient poussés et extraits du minHeap.

extrait de l'échantillon Java ressemblera à ceci:

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; 

} 

La complexité de temps est O(N log n) où n est le nombre de tableau et N est le nombre de tous les éléments dans ces tableaux.