Merge Sorted Array
Du erhältst zwei Integer-Arrays, nums1 und nums2. Jedes ist bereits in nicht absteigender Reihenfolge sortiert. Gib ein einzelnes Array zurück, das alle Werte aus beiden enthält, ebenfalls in nicht absteigender Reihenfolge. Ein Wert, der in beiden Arrays vorkommt, erscheint im Ergebnis so oft, wie er insgesamt vorkommt.
Funktion
- nums1integer-array
- das erste sortierte Array
- nums2integer-array
- das zweite sortierte Array
- Gibt zurückinteger-array
- alle Werte beider Arrays in einem sortierten Array mit der Länge nums1.length + nums2.length
Einschränkungen
1 ≤ nums1.length, nums2.length ≤ 2000-105 ≤ nums1[i], nums2[j] ≤ 105nums1undnums2sind jeweils in nicht absteigender Reihenfolge sortiert.
Beispiele
- Eingabe
- nums1 = [1, 4, 9]nums2 = [2, 3, 10]
- Ausgabe
- [1, 2, 3, 4, 9, 10]
- Erklärung
- Lies die beiden ersten Elemente und behalte das kleinere: 1, dann 2 und 3 aus
nums2, dann 4 und 9 ausnums1und zuletzt 10. Das Ergebnis enthält alle sechs Werte.
- Eingabe
- nums1 = [-5, 0, 0, 8]nums2 = [0, 6]
- Ausgabe
- [-5, 0, 0, 0, 6, 8]
- Erklärung
- Die 0 kommt in
nums1zweimal und innums2einmal vor, daher enthält das Ergebnis drei 0en. Die -5 ist kleiner als alles innums2und kommt zuerst.
- Eingabe
- nums1 = [7]nums2 = [3]
- Ausgabe
- [3, 7]
- Erklärung
- Jedes Array enthält einen Wert. 3 ist kleiner als 7, also kommt es zuerst.
+13 versteckte Tests beim Einreichen
Weiterführende Frage
Kannst du k sortierte Arrays mit insgesamt N Werten in O(N log k) Zeit zusammenführen?
Tipps
Öffne sie nacheinander. Jeder verrät ein bisschen mehr.
Beide Arrays sind bereits sortiert. Wo lässt sich der kleinste Wert des gesamten Ergebnisses finden?
Der kleinste verbleibende Wert befindet sich immer am Anfang von
nums1oder am Anfang vonnums2. Behalte für jedes Array einen Index bei, der markiert, wo sich der jeweilige Anfang befindet.Vergleiche die beiden Anfangselemente, füge das kleinere hinzu und rücke den entsprechenden Index weiter. Wenn ein Array aufgebraucht ist, ist der Rest des anderen bereits sortiert, also füge ihn unverändert hinzu.
Lösung
Die Arrays zusammenzufügen und zu sortieren liefert die richtige Antwort, aber dabei wird die Tatsache außer Acht gelassen, dass beide Hälften bereits sortiert sind. Der insgesamt kleinste verbleibende Wert steht immer am Anfang eines der beiden Arrays. Verwende je einen Index pro Array, nimm bei jedem Schritt den kleineren vorderen Wert, und in einem Durchlauf entsteht das Ergebnis. Das ist der Zusammenführungsschritt von Merge Sort.
Verketten und sortieren
Idee
Füge jeden Wert aus nums1 und jeden Wert aus nums2 in ein Array ein und sortiere es dann. Das Ergebnis enthält die richtigen Werte, jeden so oft, wie er vorkam, in der richtigen Reihenfolge.
Für [1, 4, 9] und [2, 3, 10] lautet das zusammengeführte Array [1, 4, 9, 2, 3, 10], und durch das Sortieren erhält man [1, 2, 3, 4, 9, 10].
Bei m Werten in nums1 und n in nums2 kostet eine allgemeine Sortierung O((m + n) log(m + n)). Sie funktioniert und ist für diese Grenzen schnell genug, nutzt aber nicht die sortierte Reihenfolge, die dir vorgegeben wurde. Der nächste Ansatz tut das und beseitigt den Logarithmus-Faktor.
Algorithmus
- Erstelle ein Array mit den Werten von
nums1, gefolgt von denen vonnums2. - Sortiere es in aufsteigender numerischer Reihenfolge.
- Gib es zurück.
def merge(nums1, nums2):
return sorted(nums1 + nums2)Zwei Zeiger, einer pro Array
Idee
Behalte einen Index i in nums1 und j in nums2, beide starten bei 0. Alles vor i und vor j ist bereits im Ergebnis. Der kleinste noch nicht verwendete Wert ist nums1[i] oder nums2[j], da jedes Array sortiert ist und seine verbleibenden Werte nur größer sein können. Hänge den kleineren Wert an und rücke den entsprechenden Index weiter.
Bei [1, 4, 9] und [2, 3, 10]: 1 ist kleiner als 2, dann ist 2 kleiner als 4, 3 ist kleiner als 4, 4 ist kleiner als 10 und 9 ist kleiner als 10. Nun ist nums1 vollständig verwendet, also wird der Rest von nums2, nämlich [10], unverändert kopiert. Das Ergebnis ist [1, 2, 3, 4, 9, 10].
Bei jedem Schritt wird ein Wert geschrieben, also läuft die Schleife m + n Mal: Laufzeit O(m + n). Das Ergebnisarray ist der einzige zusätzliche Speicher.
Algorithmus
- Setze
iundjauf 0 und erstelle ein leeres Ergebnis. - Vergleiche
nums1[i]mitnums2[j], solange in beiden Arrays noch Werte vorhanden sind. - Füge den kleineren Wert hinzu und rücke seinen Index weiter. Bei Gleichstand nimm
nums1[i]. - Wenn ein Array leer ist, füge die übrigen Werte des anderen hinzu.
- Gib das Ergebnis zurück.
def merge(nums1, nums2):
result = []
i = j = 0
while i < len(nums1) and j < len(nums2):
if nums1[i] <= nums2[j]:
result.append(nums1[i])
i += 1
else:
result.append(nums2[j])
j += 1
# one array is used up; the rest of the other is already sorted
result.extend(nums1[i:])
result.extend(nums2[j:])
return result
Stolperfallen und Grenzfälle
Die meisten Fehler treten auf, wenn ein Array zu Ende ist oder Werte verglichen werden.
- Die Schleife beenden, sobald ein Array aufgebraucht ist, und den Rest des anderen vergessen. Bei
[1, 2, 3]und[4, 5, 6]endet die Schleife nach 1, 2 und 3, und 4, 5, 6 müssen noch kopiert werden. nums1[i]lesen, nachdemidas Ende erreicht hat. Überprüfe beide Indizes, bevor du sie vergleichst.- Duplikate verwerfen.
[0, 0]und[0]werden zu[0, 0, 0]zusammengeführt, nicht zu[0]. - In JavaScript und TypeScript ordnet
sort()Zahlen ohne Vergleichsfunktion als Text, sodass[-5, 10, 9]zu[-5, 10, 9]sortiert wird. Übergib(a, b) => a - b. - In Lua und R beginnen Arrays bei 1, daher beginnen beide Indizes bei 1 und die Grenzen verwenden
<=.
Häufige Fragen4
Wie hoch ist die Zeitkomplexität beim Zusammenführen zweier sortierter Arrays?
Mit zwei Zeigern beträgt die Laufzeit O(m + n), wobei m und n die beiden Längen sind. Bei jedem Schritt wird ein Wert platziert, und kein Wert wird zweimal betrachtet. Das Zusammenfügen und Sortieren kostet dagegen O((m + n) log(m + n)).
Wie führst du zwei sortierte Arrays direkt zusammen?
Wenn im ersten Array am Ende Platz für beide ist, fülle es von hinten. Vergleiche die größten noch verbleibenden Werte der beiden Arrays, schreibe den größeren in den letzten freien Platz und gehe eine Position nach links. Beim Schreiben von hinten wird niemals ein Wert des ersten Arrays überschrieben, der noch nicht platziert wurde, sodass kein zweites Array benötigt wird.
Ist das Zusammenführen zweier sortierter Arrays dasselbe wie der Zusammenführungsschritt von Merge Sort?
Ja. Merge-Sort teilt ein Array in Hälften, sortiert jede Hälfte und fügt dann die beiden sortierten Hälften genau mit dieser Zwei-Zeiger-Schleife zusammen. Bei einem Gleichstand den linken Wert zu nehmen, erhält die ursprüngliche Reihenfolge gleicher Werte und macht Merge-Sort dadurch stabil.
Warum nicht die Arrays verketten und sort aufrufen?
Es liefert die richtige Antwort und ist in der Praxis oft schnell. Aber es ignoriert, dass die Eingaben bereits sortiert sind, und verursacht einen zusätzlichen log-Faktor. In einem Vorstellungsgespräch wird die Zusammenführung mit zwei Zeigern als Antwort erwartet, weil sie zeigt, dass du die vorgegebene Reihenfolge nutzen kannst.
Ähnliche Aufgaben
Aufgaben mit denselben Ideen. Wer zwei oder drei davon löst, behält das Muster.
Python
def merge(nums1, nums2):
# Schreibe hier den CodeFall 1
Fall 2
Fall 3
Eingabe
nums1 = [1, 4, 9] nums2 = [2, 3, 10]
Erwartet
[1, 2, 3, 4, 9, 10]