Java-Zwei-Zeiger-Technik

1. Übersicht

In diesem Lernprogramm wird der Zwei-Zeiger-Ansatz zur Lösung von Problemen mit Arrays und Listen erläutert. Diese Technik ist eine einfache und effiziente Möglichkeit, die Leistung unseres Algorithmus zu verbessern.

2. Beschreibung der Technik

Bei vielen Problemen mit Arrays oder Listen müssen wir jedes Element des Arrays im Vergleich zu seinen anderen Elementen analysieren.

Um solche Probleme zu lösen, beginnen wir normalerweise mit dem ersten Index und durchlaufen das Array je nach Implementierung ein- oder mehrmals. Manchmal müssen wir auch ein temporäres Array erstellen, abhängig von den Anforderungen unseres Problems.

Der obige Ansatz liefert möglicherweise das richtige Ergebnis, bietet jedoch wahrscheinlich nicht die platz- und zeiteffizienteste Lösung.

Daher ist es oft gut zu überlegen, ob unser Problem mithilfe des Zwei-Zeiger-Ansatzes effizient gelöst werden kann .

Beim Zwei-Zeiger-Ansatz beziehen sich Zeiger auf die Indizes eines Arrays. Durch die Verwendung von Zeigern können wir zwei Elemente pro Schleife anstelle von nur einem verarbeiten.

Häufige Muster beim Zwei-Zeiger-Ansatz sind:

  • Jeweils zwei Zeiger, beginnend am Anfang und am Ende, bis sich beide treffen
  • Ein Zeiger bewegt sich langsam, während sich der andere Zeiger schneller bewegt

Beide oben genannten Muster können uns dabei helfen, die zeitliche und räumliche Komplexität unserer Probleme zu verringern, da wir das erwartete Ergebnis in weniger Iterationen und ohne zu viel zusätzlichen Speicherplatz erhalten.

Schauen wir uns nun einige Beispiele an, die uns helfen, diese Technik ein bisschen besser zu verstehen.

3. Summe existiert in einem Array

Problem: Bei einem sortierten Array von Ganzzahlen müssen wir prüfen, ob zwei Zahlen darin enthalten sind, sodass ihre Summe einem bestimmten Wert entspricht.

Wenn unser Eingabearray beispielsweise [1, 1, 2, 3, 4, 6, 8, 9] und der Zielwert 11 ist , sollte unsere Methode true zurückgeben . Wenn der Zielwert jedoch 20 ist , sollte false zurückgegeben werden .

Lassen Sie uns zuerst eine naive Lösung sehen:

public boolean twoSumSlow(int[] input, int targetValue) { for (int i = 0; i < input.length; i++) { for (int j = 1; j < input.length; j++) { if (input[i] + input[j] == targetValue) { return true; } } } return false; }

In der obigen Lösung haben wir das Eingabearray zweimal durchlaufen, um alle möglichen Kombinationen zu erhalten. Wir haben die Kombinationssumme mit dem Zielwert verglichen und true zurückgegeben, wenn sie übereinstimmt. Die zeitliche Komplexität dieser Lösung beträgt O (n ^ 2) .

Nun wollen wir sehen, wie wir die Zwei-Zeiger-Technik hier anwenden können:

public boolean twoSum(int[] input, int targetValue) { int pointerOne = 0; int pointerTwo = input.length - 1; while (pointerOne < pointerTwo) { int sum = input[pointerOne] + input[pointerTwo]; if (sum == targetValue) { return true; } else if (sum < targetValue) { pointerOne++; } else { pointerTwo--; } } return false; }

Da das Array bereits sortiert ist, können wir zwei Zeiger verwenden. Ein Zeiger beginnt am Anfang des Arrays und der andere Zeiger beginnt am Ende des Arrays. Anschließend fügen wir die Werte an diesen Zeigern hinzu. Wenn die Summe der Werte kleiner als der Zielwert ist, erhöhen wir den linken Zeiger, und wenn die Summe höher als der Zielwert ist, dekrementieren wir den rechten Zeiger.

Wir bewegen diese Zeiger so lange, bis wir die Summe erhalten, die dem Zielwert entspricht, oder die Mitte des Arrays erreicht haben und keine Kombinationen gefunden wurden. Die zeitliche Komplexität dieser Lösung beträgt O (n) und die räumliche Komplexität beträgt O (1) , eine signifikante Verbesserung gegenüber unserer ersten Implementierung.

4. Array k Schritte drehen

Problem: Drehen Sie das Array bei einem gegebenen Array um k Schritte nach rechts , wobei k nicht negativ ist. Wenn beispielsweise unsere Eingänge Array [1, 2, 3, 4, 5, 6, 7] und k ist 4 , dann sollte die Ausgabe sein [4, 5, 6, 7, 1, 2, 3] .

Wir können dies lösen, indem wir wieder zwei Schleifen haben, die die Zeitkomplexität O (n ^ 2) machen, oder indem wir ein zusätzliches temporäres Array verwenden, aber das macht die Raumkomplexität O (n) .

Lösen wir dies stattdessen mit der Zwei-Zeiger-Technik:

public void rotate(int[] input, int step) { step %= input.length; reverse(input, 0, input.length - 1); reverse(input, 0, step - 1); reverse(input, step, input.length - 1); } private void reverse(int[] input, int start, int end) { while (start < end) { int temp = input[start]; input[start] = input[end]; input[end] = temp; start++; end--; } }

Bei den obigen Methoden kehren wir die Abschnitte des Eingabearrays mehrmals um, um das erforderliche Ergebnis zu erhalten. Zum Umkehren der Abschnitte haben wir den Zwei-Zeiger-Ansatz verwendet, bei dem die Elemente an beiden Enden des Array-Abschnitts ausgetauscht wurden.

Insbesondere kehren wir zuerst alle Elemente des Arrays um. Dann kehren wir die ersten k Elemente um, gefolgt vom Umkehren der restlichen Elemente. Die zeitliche Komplexität dieser Lösung beträgt O (n) und die räumliche Komplexität beträgt O (1) .

5. Mittleres Element in einer LinkedList

Problem: Suchen Sie bei einer einzeln verknüpften Liste das mittlere Element. Wenn unsere Eingabe LinkedList beispielsweise 1-> 2-> 3-> 4-> 5 ist, sollte die Ausgabe 3 sein .

Wir können die Zwei-Zeiger-Technik auch in anderen Datenstrukturen verwenden, die Arrays wie einer LinkedList ähneln :

public  T findMiddle(MyNode head) { MyNode slowPointer = head; MyNode fastPointer = head; while (fastPointer.next != null && fastPointer.next.next != null) { fastPointer = fastPointer.next.next; slowPointer = slowPointer.next; } return slowPointer.data; }

Bei diesem Ansatz durchlaufen wir die verknüpfte Liste mit zwei Zeigern. Ein Zeiger wird um eins erhöht, während der andere um zwei erhöht wird. Wenn der schnelle Zeiger das Ende erreicht, befindet sich der langsame Zeiger in der Mitte der verknüpften Liste. Die zeitliche Komplexität dieser Lösung beträgt O (n) und die räumliche Komplexität beträgt O (1) .

6. Fazit

In diesem Artikel haben wir anhand einiger Beispiele erläutert, wie wir die Zwei-Zeiger-Technik anwenden können, und untersucht, wie sie die Effizienz unseres Algorithmus verbessert.

Der Code in diesem Artikel ist auf Github verfügbar.