streamalism.org

1. Overzicht

In deze tutorial bespreken we de twee-pointer-benadering voor het oplossen van problemen met arrays en lijsten. Deze techniek is een gemakkelijke en efficiënte manier om de prestaties van ons algoritme te verbeteren.

2. Techniekbeschrijving

Bij veel problemen met arrays of lijsten moeten we elk element van de array analyseren in vergelijking met de andere elementen.

Om dit soort problemen op te lossen, beginnen we meestal bij de eerste index en doorlopen de array een of meerdere keren, afhankelijk van onze implementatie. Soms moeten we ook een tijdelijke array maken, afhankelijk van de vereisten van ons probleem.

De bovenstaande benadering geeft ons misschien het juiste resultaat, maar het geeft ons waarschijnlijk niet de meest ruimte- en tijdbesparende oplossing.

Hierdoor is het vaak goed om na te denken of ons probleem efficiënt kan worden opgelost door gebruik te maken van de tweepunts benadering.

In de twee-pointer-benadering verwijzen pointers naar de indexen van een array. Door pointers te gebruiken, kunnen we twee elementen per lus verwerken, in plaats van slechts één.

Veelvoorkomende patronen in de benadering met twee aanwijzers zijn:

• Twee tips, elk beginnend bij het begin en het einde totdat ze elkaar allebei ontmoeten
• De ene aanwijzer beweegt langzaam, terwijl de andere aanwijzer sneller beweegt

Beide bovenstaande patronen kunnen ons helpen de tijd en ruimte complexiteit van onze problemen naarmate we het verwachte resultaat krijgen in minder iteraties en zonder al te veel extra ruimte te gebruiken.

Laten we nu eens kijken naar een paar voorbeelden die ons zullen helpen deze techniek een beetje beter te begrijpen.

3. Som bestaat in een array

Probleem: Gegeven een gesorteerde reeks gehele getallen, moeten we kijken of er twee getallen in staan, zodat hun som gelijk is aan een specifieke waarde.

Als onze invoerarray bijvoorbeeld [1, 1, 2, 3, 4, 6, 8, 9] en de streefwaarde is 11, dan zou onze methode moeten terugkeren waar. Als de doelwaarde echter is 20, het zou moeten terugkeren false.

Laten we eerst een naïeve oplossing bekijken:

openbare 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 de bovenstaande oplossing hebben we de invoerarray twee keer doorgelust om alle mogelijke combinaties te krijgen. We hebben de combinatiesom vergeleken met de doelwaarde en geretourneerd waar als het overeenkomt. De tijdcomplexiteit van deze oplossing is O (n ^ 2) .

Laten we nu eens kijken hoe we de techniek met twee aanwijzers hier kunnen toepassen:

openbare 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 (som <targetValue) {pointerOne ++; } else {pointerTwo--; }} return false; }

Omdat de array al is gesorteerd, kunnen we twee pointers gebruiken. De ene pointer begint vanaf het begin van de array en de andere pointer begint vanaf het einde van de array, en dan voegen we de waarden bij deze pointers toe. Als de som van de waarden kleiner is dan de doelwaarde, verhogen we de linkerwijzer en als de som hoger is dan de doelwaarde, verlagen we de rechterwijzer.

We blijven deze aanwijzers verplaatsen totdat we de som krijgen die overeenkomt met de doelwaarde of we het midden van de array hebben bereikt en er geen combinaties zijn gevonden. De tijdcomplexiteit van deze oplossing is Aan) en de complexiteit van de ruimte is O (1), een aanzienlijke verbetering ten opzichte van onze eerste implementatie.

4. Draai de matrix k Stappen

Probleem: draai bij een gegeven array de array naar rechts met k stappen, waar k is niet negatief. Als onze invoerarray bijvoorbeeld [1, 2, 3, 4, 5, 6, 7] en k is 4, dan zou de output moeten zijn [4, 5, 6, 7, 1, 2, 3].

We kunnen dit oplossen door weer twee lussen te hebben, waardoor de tijd complexer wordt O (n ^ 2) of door een extra, tijdelijke array te gebruiken, maar dat maakt de ruimte complexer Aan).

Laten we dit oplossen met de techniek met twee aanwijzers:

public void rotate (int [] input, int step) {step% = input.length; reverse (input, 0, input.length - 1); omgekeerd (invoer, 0, stap - 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 ++; einde--; }}

Bij de bovenstaande methoden keren we de secties van de invoerarray meerdere keren op hun plaats om om het vereiste resultaat te krijgen. Voor het omkeren van de secties hebben we de twee-pointerbenadering gebruikt, waarbij elementen werden verwisseld aan beide uiteinden van de array-sectie.

Concreet keren we eerst alle elementen van de array om. Vervolgens keren we de eerste om k elementen gevolgd door het omkeren van de rest van de elementen. De tijdcomplexiteit van deze oplossing is Aan) en ruimte complexiteit is O (1).

5. Middenelement in een LinkedList

Probleem: afzonderlijk gegeven LinkedList, zoek het middelste element. Als onze input LinkedList is 1->2->3->4->5, dan zou de output moeten zijn 3.

We kunnen de two-pointer-techniek ook gebruiken in andere datastructuren die lijken op arrays zoals een LinkedList:

openbare 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; } retourneer slowPointer.data; }

Bij deze benadering doorlopen we de gekoppelde lijst met behulp van twee aanwijzingen. Een aanwijzer wordt met één verhoogd, terwijl de andere met twee wordt verhoogd. Wanneer de snelle aanwijzer het einde bereikt, staat de langzame aanwijzer in het midden van de gekoppelde lijst. De tijdcomplexiteit van deze oplossing is Aan) , en de complexiteit van de ruimte is O (1).

6. Conclusie

In dit artikel hebben we besproken hoe we de two-pointer-techniek kunnen toepassen door enkele voorbeelden te bekijken en te bekijken hoe deze de efficiëntie van ons algoritme verbetert.

De code in dit artikel is beschikbaar op Github.