Java to pointerteknik

1. Oversigt

I denne vejledning diskuterer vi tilgangen med to pointer til løsning af problemer, der involverer arrays og lister. Denne teknik er en nem og effektiv måde at forbedre vores algoritmes ydeevne på.

2. Teknikbeskrivelse

I mange problemer, der involverer arrays eller lister, er vi nødt til at analysere hvert element i arrayet sammenlignet med dets andre elementer.

For at løse problemer som disse starter vi normalt fra det første indeks og løber gennem arrayet en eller flere gange afhængigt af vores implementering. Nogle gange er vi også nødt til at oprette et midlertidigt array afhængigt af vores problemkrav.

Ovenstående fremgangsmåde kan give os det korrekte resultat, men det vil sandsynligvis ikke give os den mest plads- og tidseffektive løsning.

Som et resultat er det ofte godt at overveje, om vores problem kan løses effektivt ved hjælp af to-pointer tilgang.

I tilgangen med to pointer henviser markører til en matrixs indekser. Ved at bruge pegepinde kan vi behandle to elementer pr. Løkke i stedet for kun en.

Almindelige mønstre i to-peger tilgang involverer:

  • To pegepinde, der hver starter fra begyndelsen og slutningen, indtil de begge mødes
  • En markør bevæger sig i et langsomt tempo, mens den anden markør bevæger sig i et hurtigere tempo

Begge ovenstående mønstre kan hjælpe os med at reducere tid og rum kompleksitet af vores problemer, da vi får det forventede resultat i færre iterationer og uden at bruge for meget ekstra plads.

Lad os nu se på et par eksempler, der hjælper os med at forstå denne teknik lidt bedre.

3. Sum findes i en matrix

Problem: Givet et sorteret array af heltal, skal vi se, om der er to tal i det, således at deres sum er lig med en bestemt værdi.

For eksempel, hvis vores input array er [1, 1, 2, 3, 4, 6, 8, 9] og målværdien er 11, så skulle vores metode vende tilbage rigtigt. Men hvis målværdien er 20, det skal vende tilbage falsk.

Lad os først se en naiv løsning:

offentlig boolsk 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 sand; }}} returner falsk; }

I ovenstående løsning sløjfede vi to gange over inputmatrixen for at få alle mulige kombinationer. Vi kontrollerede kombinationssummen mod målværdien og returnerede rigtigt hvis det matcher. Tids kompleksiteten af ​​denne løsning er O (n ^ 2) .

Lad os nu se, hvordan vi kan anvende to-pegeteknikken her:

offentlig boolsk twoSum (int [] input, int targetValue) {int pointerOne = 0; int pointerTwo = input.length - 1; mens (pointerOne <pointerTwo) {int sum = input [pointerOne] + input [pointerTwo]; if (sum == targetValue) {return true; } ellers hvis (sum <targetValue) {pointerOne ++; } andet {pointerTwo--; }} returner falsk; }

Da arrayet allerede er sorteret, kan vi bruge to markører. Den ene markør starter fra begyndelsen af ​​arrayet, og den anden markør begynder fra slutningen af ​​arrayet, og derefter tilføjer vi værdierne ved disse markører. Hvis summen af ​​værdierne er mindre end målværdien, øges den venstre markør, og hvis summen er højere end målværdien, mindskes den højre markør.

Vi fortsætter med at flytte disse markører, indtil vi får summen, der matcher målværdien, eller hvis vi har nået midten af ​​arrayet, og der ikke er fundet nogen kombinationer. Tids kompleksiteten af ​​denne løsning er På) og rumkompleksitet er O (1), en betydelig forbedring i forhold til vores første implementering.

4. Drej Array k Trin

Problem: Givet et array, drej arrayet til højre ved k trin, hvor k er ikke-negativ. For eksempel, hvis vores input array er [1, 2, 3, 4, 5, 6, 7] og k er 4, så skal output være [4, 5, 6, 7, 1, 2, 3].

Vi kan løse dette ved at have to sløjfer igen, hvilket gør tidskompleksiteten O (n ^ 2) eller ved at bruge et ekstra, midlertidigt array, men det vil gøre pladsens kompleksitet På).

Lad os løse dette ved hjælp af to-pointer-teknikken i stedet:

public void rotate (int [] input, int step) {step% = input.length; omvendt (input, 0, input.længde - 1); omvendt (input, 0, trin - 1); omvendt (input, trin, input.længde - 1); } privat ugyldigt omvendt (int [] input, int start, int slut) {while (start <end) {int temp = input [start]; input [start] = input [slut]; input [slut] = temp; start ++; ende--; }}

I ovenstående metoder vender vi sektionerne i inputmatrixen på plads flere gange for at få det krævede resultat. Til at vende sektionerne brugte vi to-pegermetoden, hvor udskiftning af elementer blev udført i begge ender af array-sektionen.

Specifikt vender vi først alle elementerne i arrayet. Derefter vender vi den første om k elementer efterfulgt af omvendt resten af ​​elementerne. Tids kompleksiteten af ​​denne løsning er På) og rumkompleksitet er O (1).

5. Mellemelement i a LinkedList

Problem: Givet en enkelt LinkedList, find dets midterste element. For eksempel hvis vores input LinkedList er 1->2->3->4->5, så skal output være 3.

Vi kan også bruge to-peger-teknikken i andre datastrukturer, der ligner arrays som a LinkedList:

public T findMiddle (MyNode head) {MyNode slowPointer = head; MyNode fastPointer = hoved; mens (fastPointer.next! = null && fastPointer.next.next! = null) {fastPointer = fastPointer.next.next; slowPointer = slowPointer.next; } returner slowPointer.data; }

I denne tilgang krydser vi den sammenkædede liste ved hjælp af to markører. Den ene markør forøges med den ene, mens den anden øges med to. Når den hurtige markør når slutningen, vil den langsomme markør være midt på den sammenkædede liste. Tids kompleksiteten af ​​denne løsning er På) , og rumkompleksitet er O (1).

6. Konklusion

I denne artikel diskuterede vi, hvordan vi kan anvende topointerteknikken ved at se nogle eksempler og se på, hvordan det forbedrer effektiviteten af ​​vores algoritme.

Koden i denne artikel er tilgængelig på Github.


$config[zx-auto] not found$config[zx-overlay] not found