Führen Sie zwei sortierte Listen in Python zusammen

1. Führen Sie zwei sortierte Listen in Python zusammen
2. Naiver Ansatz zum Zusammenführen zweier sortierter Listen in Python
3. Führen Sie zwei sortierte Listen mit der Methode heapq.merge() in Python zusammen
4. Führen Sie zwei sortierte Listen mit der Funktion sorted() in Python zusammen
5. Abschluss

Sortierte Listen sind diejenigen, die entweder in aufsteigender oder absteigender Reihenfolge angeordnet sind, und das Zusammenführen dieser sortierten Listen bezieht sich darauf, beide Listen so zu kombinieren, dass sie sortiert bleiben.

Es gibt verschiedene Methoden in Python, in denen wir die beiden sortierten Listen zusammenführen können. Python hat eingebaute Funktionen zum Ausführen dieser Aufgabe, aber wir werden auch den naiven Ansatz besprechen, der verwendet wird, um diese eingebauten Funktionen zu entwerfen.

Führen Sie zwei sortierte Listen in Python zusammen

In diesem Artikel erhalten wir eine Problemstellung und werden gebeten, eine Lösung dafür zu entwerfen. Das Problem ist, dass wir zwei Listen haben, die einzeln sortiert sind, aber wir müssen sie zusammenführen, um nach dem Zusammenführen sortiert zu bleiben.

Lassen Sie uns dies anhand eines Beispiels verstehen.

list1 = [2, 5, 7, 8, 9]
list2 = [0, 1, 3, 4, 6]

Ausgang:

Sorted List: [0,1,2,3,4,5,6,7,8,9]

Die sortierte Liste in der Ausgabe setzt sich aus den Elementen der Listen list1 und list2 zusammen. Nach dem Zusammenführen werden sie so angeordnet, dass die kombinierte Liste immer noch sortiert ist.

Dieses Problem ist das gleiche wie das Entwerfen der merge-Funktion, die beim Merge-Sortieren verwendet wird. Daher stoßen wir bei der Lösung dieser Fragen häufig auf diese Art von Problem.

Daher sollten wir eine grundlegende Vorstellung davon haben, wie wir damit umgehen. Lassen Sie uns nun verstehen, wie wir dieses Problem lösen werden.

Naiver Ansatz zum Zusammenführen zweier sortierter Listen in Python

Die Lösung, die wir diskutieren werden, ist ein naiver Ansatz, der die beiden sortierten Listen in Python zusammenführt. Bei diesem Ansatz durchlaufen wir beide Listen gleichzeitig und suchen nach dem kleineren Element zwischen den beiden Elementen an der aktuellen Position.

Das kleinere Element wird an die Antwort angehängt. Wenn jedoch eine der beiden Listen vollständig durchlaufen wird, wird die andere Liste nach den zusammengeführten Elementen an das Ergebnis angehängt.

Lassen Sie uns den Code sehen, um ihn besser zu verstehen.

firstList = [2, 7, 8, 9]
secondList = [0, 1, 4, 6]
result = []
i, j = 0, 0

while i < len(firstList) and j < len(secondList):
    if firstList[i] < secondList[j]:
        result.append(firstList[i])
        i = i + 1
    else:
        result.append(secondList[j])
        j = j + 1

result = result + firstList[i:] + secondList[j:]
print("Sorted List: " + str(result))

Ausgang:

Sorted List: [0, 1, 2, 4, 6, 7, 8, 9]

Wir haben im obigen Code eine leere Liste als Ergebnis deklariert, die unsere zusammengeführte Liste speichern wird. Wir haben dann beide Listen durchlaufen, bis eine von ihnen oder beide erschöpft sind.

Innerhalb der Schleife vergleichen wir die Elemente aus beiden Listen und hängen das kleinere Element an unsere Ergebnis-Variable an, wonach wir den aktuellen Index um 1 erhöhen.

Wenn eine der Listen Elemente enthält, die nicht in unserem Ergebnis enthalten sind, führen wir die verbleibenden Elemente mit dem Slicing-Operator in Python in unsere Antwort ein.

Bei diesem Ansatz haben wir die Listen nur einmal durchlaufen; daher hat es eine Zeitkomplexität von O(n1+n2), während die Raumkomplexität für den obigen Ansatz ebenfalls O(n1+n2) ist, wobei sich n1 und n2 auf die Größen der Sortierung beziehen Listen.

Führen Sie zwei sortierte Listen mit der Methode heapq.merge() in Python zusammen

Das Modul heapq in Python bezieht sich auf die Heap-Warteschlange. Dieses Modul Heapq wird jedoch hauptsächlich verwendet, um die Prioritätswarteschlange in Python zu implementieren.

Das Modul heapq enthält die Funktion merge() in Python, die mehrere sortierte Listen als Argument akzeptiert und eine einzelne kombinierte, zusammengeführte Liste zurückgibt.

Lassen Sie uns sehen, wie wir die Merge-Operation mit der Funktion heapq.merge() in Python durchführen können.

from heapq import merge

first = [2, 7, 8, 9]
second = [0, 1, 4, 6]

res = list(merge(first, second))

print("Merged Sorted list: ", str(res))

Ausgang:

Merged Sorted list:  [0, 1, 2, 4, 6, 7, 8, 9]

Im obigen Code haben wir die beiden sortierten Listen first und second in der Funktion merge() als Argument übergeben, danach wandeln wir sie explizit in eine Liste um. Als Ergebnis wird die zusammengeführte sortierte Liste in der Variablen ans gespeichert.

Wie wir sehen, können wir die Funktion merge() des Moduls heapq verwenden, um zwei sortierte Listen in Python zusammenzuführen.

Führen Sie zwei sortierte Listen mit der Funktion sorted() in Python zusammen

Pythons sorted()-Funktion sortiert die als Parameter übergebenen Listen oder Tupel. Es gibt immer eine Liste zurück, die sortiert wird, ohne die ursprüngliche Reihenfolge zu ändern.

Mit dieser Funktion können wir unser Problem in nur einer Zeile lösen. Wir hängen beide Listen zusammen und wenden dann die Funktion sorted() auf die resultierende Liste an.

Lassen Sie es uns anhand eines Beispiels verstehen.

first = [2, 7, 9]
second = [0, 1, 4]

result = sorted(first + second)

print("List after sorting: ", str(result))

Ausgang:

List after sorting:  [0, 1, 2, 4, 7, 9]

Im obigen Programm haben wir den Operator + verwendet, um die beiden Listen aneinander anzuhängen. Der Verkettungsoperator + wird verwendet, um mehrere Listen in der Reihenfolge, in der sie in den Code eingegeben wurden, zu einer einzigen kombinierten Liste anzuhängen.

Danach haben wir die Funktion sorted() auf die angehängte Liste angewendet, die die Sequenz sortiert und das Ergebnis druckt.

Dieser Ansatz kann mehr Zeit in Anspruch nehmen, da wir intern zwei Listen an eine einzige Liste anhängen, was mehr Zeit in Anspruch nimmt als die beiden anderen oben besprochenen Ansätze.

Abschluss

Dieser Artikel beschreibt die verschiedenen Ansätze, mit denen wir zwei sortierte Listen in Python zusammenführen können. Zwei davon sind in Python eingebaute Methoden, während die andere eine detaillierte Herangehensweise an das Problem ist.

Die Funktion sorted() ist eine der eingebauten Funktionen zum Sortieren der angehängten Listen, während die andere Funktion heapq.merge() eine Methode zum Zusammenführen der beiden sortierten Listen in Python ist. Beide Funktionen können die Operationen in einer einzelnen Zeile ausführen.

Der detaillierte Ansatz besteht darin, die Listen zu durchlaufen, jedes Element am aktuellen Index zu vergleichen, das kleinere Element an die Antwort anzuhängen und dann den aktuellen Index um 1 zu erhöhen. Diese Schleife läuft, bis eine oder beide Listen erschöpft sind, danach die verbleibenden Elemente werden durch den Slicing-Operator von Python angehängt.

Sie können eine der oben beschriebenen Methoden verwenden, um das Problem zu lösen.