Problemlösungsmuster

Willkommen zurück zu unserer Blogreihe zum Thema Problemlösung in der modernen Softwareentwicklung!

In Teil 1 haben wir das Frequency Counter Pattern untersucht, eine leistungsstarke Technik zur Optimierung von Algorithmen durch effizientes Zählen der Häufigkeit von Elementen. Wenn Sie es verpasst haben oder eine kurze Auffrischung wünschen, können Sie es sich gerne ansehen, bevor Sie fortfahren.

In diesem Teil befassen wir uns mit einem weiteren wesentlichen Muster: dem Multipointer-Muster. Dieses Muster ist von unschätzbarem Wert, wenn es um Szenarien geht, in denen mehrere Elemente gleichzeitig verglichen, durchsucht oder durchlaufen werden müssen. Lassen Sie uns untersuchen, wie es funktioniert und wo Sie es anwenden können, um die Effizienz Ihres Codes zu verbessern.

02. Multipointer-Muster

Das Multipointer-Muster ist eine Technik, die beim Algorithmusdesign verwendet wird, bei der mehrere Zeiger (oder Iteratoren) verwendet werden, um Datenstrukturen wie Arrays oder verknüpfte Listen zu durchlaufen. Anstatt sich auf einen einzelnen Zeiger oder eine einzelne Schleife zu verlassen, verwendet dieses Muster zwei oder mehr Zeiger, die sich mit unterschiedlichen Geschwindigkeiten oder von unterschiedlichen Startpunkten aus durch die Daten bewegen.

Beispielproblem

Schreiben Sie eine Funktion namens sumZero, die ein sortiertes Array von Ganzzahlen akzeptiert. Die Funktion sollte das erste Paar finden, bei dem die Summe Null ist. Wenn ein solches Paar vorhanden ist, wird ein Array zurückgegeben, das beide Werte enthält. Andernfalls geben Sie undefiniert zurück.

sumZero([-3,-2,-1,0,1,2,3]) //output: [-3, 3]
sumZero([-2,0,1,3]) //output: undefined
sumZero([-4, -3, -2, -1, 0, 1, 2, 5]) //output: [-2, 2]

Basislösung

function sumZero(arr){
    for (let i = 0; i < arr.length; i++) {
        for (let j = i+1; j < arr.length; j++) {
            if (arr[i] + arr[j] === 0) {
                console.log(arr[i] + arr[j])
                return [arr[i], arr[j]]
            }
        }
    }
}

Zeitkomplexität - O(N^2)

Lösung mit Multipointer-Muster

Schritt 1: Verstehen Sie das Problem
Wir müssen zwei Zahlen in einem **sortierten Array finden, deren Summe Null ergibt. Da das Array sortiert ist, können wir diese Reihenfolge nutzen, um die Lösung effizienter zu finden.

Schritt 2: Zwei Zeiger initialisieren
Richten Sie zwei Zeiger ein: einen (links) beginnend am Anfang des Arrays und einen (rechts) beginnend am Ende.

Beispiel:

Array: [-4, -3, -2, -1, 0, 1, 2, 5]
Left Pointer (L): -4
Right Pointer (R): 5

Schritt 3: Berechnen Sie die Summe der Werte an den Zeigern
Addieren Sie die Werte am linken und rechten Zeiger, um die Summe zu erhalten

Sum = -4 + 5 = 1

Schritt 4: Vergleichen Sie die Summe mit Null

• Wenn die Summe größer als Null ist: Bewegen Sie den rechten Zeiger einen Schritt nach links, um die Summe zu verringern.

Sum is 1 > 0, so move the right pointer left:

Array: [-4, -3, -2, -1, 0, 1, 2, 5]
Left Pointer (L): -4
Right Pointer (R): 2

• Wenn die Summe kleiner als Null ist: Bewegen Sie den linken Zeiger einen Schritt nach rechts, um die Summe zu erhöhen.

New Sum = -4 + 2 = -2
Sum is -2 < 0, so move the left pointer right:

Array: [-4, -3, -2, -1, 0, 1, 2, 5]
Left Pointer (L): -3
Right Pointer (R): 2

Schritt 5: Wiederholen Sie den Vorgang
Bewegen Sie die Zeiger weiter und berechnen Sie die Summe, bis sie sich treffen oder ein Paar gefunden wird.

New Sum = -3 + 2 = -1
Sum is -1 < 0, so move the left pointer right:

Array: [-4, -3, -2, -1, 0, 1, 2, 5]
Left Pointer (L): -2
Right Pointer (R): 2

Die Summe ist Null, daher gibt die Funktion [-2, 2] zurück.

Wenn die Schleife abgeschlossen wird, ohne ein solches Paar zu finden, geben Sie undefiniert zurück.

Endgültiger Code

function sumZero(arr) {
  let left = 0;                         // Initialize the left pointer at the start of the array
  let right = arr.length - 1;           // Initialize the right pointer at the end of the array

  while (left < right) {                // Continue until the pointers meet
    const sum = arr[left] + arr[right]; // Calculate the sum of the values at the pointers

    if (sum === 0) {                    // If the sum is zero, return the pair
      return [arr[left], arr[right]];
    } else if (sum > 0) {               // If the sum is greater than zero, move the right pointer left
      right--;
    } else {                            // If the sum is less than zero, move the left pointer right
      left++;
    }
  }

  return undefined;                     // If no pair is found, return undefined
}

HINWEIS:
Zeitkomplexität: O(n) – Die Funktion ist effizient und skaliert linear mit der Größe des Arrays.
Raumkomplexität: O(1) – Die Funktion benötigt nur minimalen zusätzlichen Speicher.

Fazit

Das Multipointer-Muster ist eine leistungsstarke Technik zur Lösung von Problemen, bei denen Elemente in einer sortierten Datenstruktur gesucht, verglichen oder bearbeitet werden. Durch die Verwendung mehrerer Zeiger, die sich aufeinander zubewegen, können wir die Effizienz von Algorithmen erheblich verbessern und in vielen Fällen die Zeitkomplexität von O(n²) auf O(n) reduzieren. Dieses Muster ist vielseitig und kann auf eine Vielzahl von Problemen angewendet werden, was es zu einer wesentlichen Strategie zur Optimierung der Leistung Ihres Codes macht.

Bleiben Sie gespannt auf unseren nächsten Beitrag, in dem wir uns mit dem Sliding Window Pattern befassen, einem weiteren wichtigen Werkzeug zur Lösung von Problemen mit dynamischen Datensegmenten. Es ist ein unglaublich nützliches Muster, das Ihnen helfen kann, sogar komplexere Herausforderungen mit Leichtigkeit zu lösen!

Das obige ist der detaillierte Inhalt vonProblemlösungsmuster. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!