Verschmelzung unbekannter Anzahl von Arrays

Mein Problem ist, ist es möglich, (unbekannte Anzahl von Arrays) zu einem einzigen Array zu verschmelzen.so kenne ich nicht die Anzahl der Arrays genau (nicht wie Mergen von zwei Array Merging n Array usw.) Unterschrift:Verschmelzung unbekannter Anzahl von Arrays

> int [] merge(int k)//k is number of arrays to be merged into a one 
    > merge them 
    //and so on.. 
    > 
    > return array;

Quelle

2012-03-30 rena-c

Coole Aufgabe, und was hast du probiert? –

kennen Sie die Anzahl der Arrays. es ist k :). Gibt es eine Regel beim Zusammenführen? – UmNyobe

Ich arbeite an Sortierung Array in einem verteilten Netzwerk.Sie in k Partitionen aufgeteilt, sortiert auf Server-Seite und verschmolzen auf der Client-Seite.Problem ist ich weiß nicht, # der Arrays zusammengeführt werden. –

Wenn Sie wissen, wie 2-Arrays zu verbinden, dann können Sie eine beliebige Anzahl von Arrays verschmelzen;)

Quelle

2012-03-30 09:48:45 saadtaame

sicher, fusionieren Feld 1 mit Array 2, Matrix 1 + 2 mit 3-Array verschmelzen, Verschmelzen Sie das Array 1 + 2 + 3 mit dem Array 4, und fahren Sie fort, bis Sie keine Arrays mehr haben. Sie benötigen lediglich eine Methode zum Zusammenführen von 2 Arrays und eine Methode zum Aufrufen dieses Arrays mit einer Liste von Arrays, bis die Liste leer ist.

Quelle

2012-03-30 09:49:18

Das wäre O (kn^2), viel langsamer als die von amit vorgeschlagene k-way merge. Aber dann wieder - es sieht so aus, als müssten Sie k kennen, um k-way merge zu verwenden, denn obwohl diese Methode langsam ist, müssen Sie k nicht kennen, um es zu implementieren. – Dan

diese Idee kam mir in den Sinn :) aber es ist nicht effizient. –

Hmmm, ich denke es ist O (k * n * log (n)) aber Effizienz ist nicht alles: k-way Merge ist effizienter, aber ich denke du musst k wissen um zu beginnen. –

Ja, es ist möglich und für k Arrays ist es in der Regel mit einer Prioritätswarteschlange der Größe k getan. Die Warteschlange enthält ein Element aus jedem Array (zusammen mit einem Tag zum Erinnern, aus welchem Array das Element stammt).

Anfänglich ist die Warteschlange mit dem minimalen Element aus jedem Array gefüllt. Dann entfernen Sie iterativ das minimale Element aus der Warteschlange und fügen das nächste Element zur Warteschlange hinzu, aus dem Array, aus dem das letzte minimale Element stammt.

Unter der Annahme der Standard-Heap-Implementierung der Warteschlange ergibt dies O (nlog (k)) -Komplexität.

Quelle

2012-03-30 09:51:09

Obwohl es möglich ist, um iterativ Arrays zu fusionieren, eine effizientere Art und Weise wird ein k-way merge, sein, die in O(nlogk) erfolgt, bei k die Anzahl von Arrays und n ist die Gesamtzahl von Elementen, eine Prioritäts-Warteschlange verwendet wird.

Hinweis: Es kann nicht besser als O(nlogk) getan werden, denn wenn es möglich ist [die mit Komplexität sagen lassen O(g(n)) wo g(n) als asymptotisch schwächer dann ist nlogn] - dann können wir den folgenden Sortieralgorithmus erzeugen:

sort(array A): 
    split A into n arrays, each of size 1, B1,...,Bn 
    A <- special_merge(B1,...Bn) 
    return A

Es ist leicht zu sehen, dass dieser Algorithmus der Komplexität ist O(g(n) + n) = O(g(n)), und wir bekommen eine contraditcion, da wir eine Art besser als O(nlogn) bekamen - die mit compartions basierten Algorithmen nicht möglich ist, da dieses Problem Omega(nlogn) ist

Quelle

2012-03-30 09:52:28 amit

Verschmelzung unbekannter Anzahl von Arrays

Antwort

Verwandte Themen