LeetCode-Herausforderung: Sortierte Arrays zusammenführen – JavaScript-Lösung

Top Interview 150

Das Zusammenführen sortierter Arrays ist ein klassisches Problem, und für die Codierung von Interviews ist es wichtig zu verstehen, wie man es effizient löst. In diesem Beitrag befassen wir uns mit LeetCodes 88. Merge Sorted Array, einem Teil der Top-Interview-150-Fragen-Challenge, unter Verwendung von JavaScript. Tauchen wir ein in das Problem, seine Nuancen und eine saubere, optimale Lösung!

? Problembeschreibung
Sie erhalten zwei ganzzahlige Arrays nums1 und nums2, sortiert in nicht absteigender Reihenfolge. Ihre Aufgabe besteht darin, nums2 mit nums1 zusammenzuführen, sodass nums1 sortiert bleibt.

Es gibt jedoch eine Wendung:

nums1 verfügt über genügend Platz (auf 0 gesetzt), um die Elemente von nums2 aufzunehmen.
Das endgültige zusammengeführte Ergebnis muss direkt in nums1.

? Beispiele

Beispiel 1

Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
Output: [1,2,2,3,5,6]

Beispiel 2

Input: nums1 = [1], m = 1, nums2 = [], n = 0
Output: [1]

Beispiel 3

Input: nums1 = [0], m = 0, nums2 = [1], n = 1
Output: [1]

? Wichtige Erkenntnisse

• In-Place-Zusammenführung: Sie müssen nums1 füllen, ohne zusätzlichen Platz zu beanspruchen. Dies bedeutet, dass das Array direkt geändert werden muss.
• Strategie von hinten nach vorne: Da nums1 am Ende zusätzlichen Platz hat, besteht der effizienteste Ansatz darin, ihn von hinten zu füllen.

? JavaScript-Lösung: Zwei-Zeiger-Ansatz

Die optimale Lösung nutzt einen Zwei-Zeiger-Ansatz, beginnend am Ende beider Arrays. Dadurch wird sichergestellt, dass die größten Elemente zuerst platziert werden, wodurch unnötige Verschiebungen von Elementen vermieden werden.

var merge = function(nums1, m, nums2, n) {
    // Initialize pointers for nums1, nums2, and the last index of nums1
    let p1 = m - 1;
    let p2 = n - 1;
    let p = m + n - 1;

    // Compare elements from the end and place the largest at the back
    while (p1 >= 0 && p2 >= 0) {
        if (nums1[p1] > nums2[p2]) {
            nums1[p] = nums1[p1];
            p1--;
        } else {
            nums1[p] = nums2[p2];
            p2--;
        }
        p--;
    }

    // Copy remaining elements from nums2 (if any)
    while (p2 >= 0) {
        nums1[p] = nums2[p2];
        p2--;
        p--;
    }
};

? Wie es funktioniert

1. Beginnen Sie am Ende:
   Vergleichen Sie die größten Elemente von nums1 und nums2 (mit p1
   ). und p2-Zeiger). Platzieren Sie das größere Element am Ende von
   nums1 (mit p-Zeiger).

2. Zeiger dekrementieren:
   Verschieben Sie p1, p2 und p, während Sie Elemente verarbeiten.

3. Verbleibende Elemente verwalten:
   Wenn noch Elemente in „nums2“ übrig sind, kopieren Sie sie in „nums1“. (Nein
   müssen Elemente aus nums1 kopieren, da sie bereits vorhanden sind.)

? Komplexitätsanalyse

? Trockenlauf
Eingabe:
Anzahl1 = [1,2,3,0,0,0], m = 3, Anzahl2 = [2,5,6], n = 3

Schritt p1 p2 p nums1
Init 2 2 5 [1,2,3,0,0,0]
1 2 2 5 [1,2,3,0,0,6]
2 2 1 4 [1,2,3,0,5,6]
3 2 0 3 [1,2,3,3,5,6]
4 1 0 2 [1,2,2,3,5,6]
5 0 0 1 [1,2,2,3,5,6]
Endgültige Ausgabe: [1,2,2,3,5,6]

? Probieren Sie es selbst aus!

Sehen Sie sich die vollständigen Problem- und Testfälle auf LeetCode an. Fordern Sie sich heraus, die Lösung zu implementieren, ohne einen Blick auf den Code zu werfen!

✨ Profi-Tipps für Vorstellungsgespräche

1. Einschränkungen klären: Fragen Sie, ob Sie zusätzlichen Platz nutzen können oder ob Platz ist Pflicht.
2. Für Randfälle optimieren: Berücksichtigen Sie Fälle, in denen nums2 leer ist oder nums1 hat keine Anfangselemente (m = 0).
3. Gehen Sie Ihre Logik durch: Erklären Sie den Zwei-Punkte-Ansatz eindeutig an den Interviewer.

Haben Sie Fragen oder Erkenntnisse? Teilen Sie sie in den Kommentaren unten! Lasst uns gemeinsam lernen. ?

Das obige ist der detaillierte Inhalt vonLeetCode-Herausforderung: Sortierte Arrays zusammenführen – JavaScript-Lösung. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!