streamalism.org

1. Oversikt

I denne veiledningen vil vi diskutere topeker-tilnærmingen for å løse problemer som involverer matriser og lister. Denne teknikken er en enkel og effektiv måte å forbedre ytelsen til algoritmen vår på.

2. Teknikkbeskrivelse

I mange problemer som involverer matriser eller lister, må vi analysere hvert element i matrisen sammenlignet med de andre elementene.

For å løse problemer som disse starter vi vanligvis fra den første indeksen og går gjennom matrisen en eller flere ganger, avhengig av implementeringen. Noen ganger må vi også lage en midlertidig matrise avhengig av problemets krav.

Ovennevnte tilnærming kan gi oss det riktige resultatet, men det vil sannsynligvis ikke gi oss den mest plass- og tidseffektive løsningen.

Som et resultat er det ofte bra å vurdere om problemet vårt kan løses effektivt ved å bruke topekere nærmer seg.

I topeker-tilnærmingen refererer pekere til en matrise indekser. Ved å bruke pekere kan vi behandle to elementer per sløyfe, i stedet for bare ett.

Vanlige mønstre i topeker-tilnærmingen innebærer:

• To pekere som begynner fra begynnelsen og slutten til de begge møtes
• Den ene pekeren beveger seg i sakte tempo mens den andre pekeren beveger seg i et raskere tempo

Begge de ovennevnte mønstrene kan hjelpe oss med å redusere tid og rom kompleksitet av våre problemer da vi får forventet resultat i færre iterasjoner og uten å bruke for mye ekstra plass.

La oss nå se på noen få eksempler som vil hjelpe oss til å forstå denne teknikken litt bedre.

3. Sum eksisterer i en serie

Problem: Gitt et sortert utvalg av heltall, må vi se om det er to tall i det slik at summen er lik en bestemt verdi.

For eksempel hvis vårt inngangssett er [1, 1, 2, 3, 4, 6, 8, 9] og målverdien er 11, så skal metoden vår komme tilbake ekte. Imidlertid, hvis målverdien er 20, den skal komme tilbake falsk.

La oss 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 true; }}} returner falsk; }

I løsningen ovenfor slo vi to ganger over inngangsruten for å få alle mulige kombinasjoner. Vi sjekket kombinasjonssummen mot målverdien og returnerte ekte hvis det stemmer overens. Tidenes kompleksitet i denne løsningen er O (n ^ 2) .

La oss nå se hvordan vi kan bruke topekerteknikken 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]; hvis (sum == targetValue) {return true; } ellers hvis (sum <targetValue) {pointerOne ++; } annet {pointerTwo--; }} returner falsk; }

Siden matrisen allerede er sortert, kan vi bruke to pekere. Den ene pekeren starter fra begynnelsen av matrisen, og den andre pekeren begynner fra slutten av matrisen, og deretter legger vi til verdiene i disse pekerne. Hvis summen av verdiene er mindre enn målverdien, øker vi venstre peker, og hvis summen er høyere enn målverdien, reduseres den høyre pekeren.

Vi fortsetter å flytte disse pekerne til vi får summen som samsvarer med målverdien, eller hvis vi har nådd midten av matrisen, og ingen kombinasjoner er funnet. Tidenes kompleksitet i denne løsningen er På) og romkompleksitet er O (1), en betydelig forbedring i forhold til vår første implementering.

4. Roter Array k Fremgangsmåte

Problem: Gitt en matrise, roter matrisen til høyre ved k trinn, hvor k er ikke-negativ. For eksempel hvis vårt inngangssett er [1, 2, 3, 4, 5, 6, 7] og k er 4, så skal utgangen være [4, 5, 6, 7, 1, 2, 3].

Vi kan løse dette ved å ha to løkker igjen som vil gjøre tidskompleksiteten O (n ^ 2) eller ved å bruke en ekstra, midlertidig matrise, men det vil gjøre plassen kompleksitet På).

La oss løse dette ved hjelp av topeker-teknikken i stedet:

public void rotate (int [] input, int step) {step% = input.length; revers (input, 0, input.length - 1); revers (inngang, 0, trinn - 1); revers (input, step, input.length - 1); } privat ugyldig omvendt (int [] input, int start, int end) {while (start <end) {int temp = input [start]; input [start] = input [end]; inngang [slutt] = temp; start ++; slutt--; }}

I de ovennevnte metodene reverserer vi delene av inngangsmatrisen på plass flere ganger for å få det nødvendige resultatet. For å reversere seksjonene brukte vi topeker-tilnærmingen der bytte av elementer ble gjort i begge ender av matriseseksjonen.

Spesielt reverserer vi først alle elementene i matrisen. Deretter reverserer vi den første k elementer etterfulgt av å reversere resten av elementene. Tidenes kompleksitet i denne løsningen er På) og romkompleksitet er O (1).

5. Midtre element i en LinkedList

Problem: Gitt en enkelt LinkedList, finn midtelementet. For eksempel hvis våre innspill LinkedList er 1->2->3->4->5, da skal utgangen være 3.

Vi kan også bruke topekerteknikken i andre datastrukturer som ligner på matriser som en LinkedList:

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

I denne tilnærmingen krysser vi den koblede listen ved hjelp av to pekere. Den ene pekeren økes med den ene, mens den andre økes med to. Når hurtigpekeren når slutten, vil den langsomme pekeren være midt på den koblede listen. Tidenes kompleksitet i denne løsningen er På) , og romkompleksitet er O (1).

6. Konklusjon

I denne artikkelen diskuterte vi hvordan vi kan bruke topekerteknikken ved å se noen eksempler og så på hvordan det forbedrer effektiviteten til algoritmen vår.

Koden i denne artikkelen er tilgjengelig på Github.