Technika Java Two Pointer

1. Prehľad

V tejto príručke sa budeme zaoberať prístupom dvoch ukazovateľov pri riešení problémov týkajúcich sa polí a zoznamov. Táto technika predstavuje ľahký a efektívny spôsob, ako zlepšiť výkonnosť nášho algoritmu.

2. Opis techniky

Pri mnohých problémoch týkajúcich sa polí alebo zoznamov musíme analyzovať každý prvok poľa v porovnaní s jeho ostatnými prvkami.

Na vyriešenie problémov, ako sú tieto, obvykle začíname od prvého indexu a po jednom alebo viacerých cykloch prechádzame po poli v závislosti od našej implementácie. Niekedy tiež musíme vytvoriť dočasné pole v závislosti od požiadaviek nášho problému.

Vyššie uvedený prístup by nám mohol poskytnúť správny výsledok, ale pravdepodobne nám neprinesie priestorovo a časovo najefektívnejšie riešenie.

Vo výsledku je často dobré zvážiť, či je možné náš problém efektívne vyriešiť pomocou dvojbodový prístup.

V prístupe s dvoma ukazovateľmi sa ukazovatele vzťahujú na indexy poľa. Pomocou ukazovateľov môžeme spracovať dva prvky na jednu slučku, nielen jeden.

Bežné vzorce prístupu založeného na dvoch ukazovateľoch zahŕňajú:

  • Dva ukazovatele, každý od začiatku a do konca, kým sa obaja nestretnú
  • Jeden ukazovateľ sa pohybuje pomalým tempom, zatiaľ čo druhý sa pohybuje rýchlejšie

Oba vyššie uvedené vzory nám môžu pomôcť znížiť časová a priestorová zložitosť keď dostaneme očakávaný výsledok, bude mať menej iterácií a nebude potrebné využívať príliš veľa ďalšieho priestoru.

Poďme sa teraz pozrieť na niekoľko príkladov, ktoré nám pomôžu pochopiť túto techniku ​​o niečo lepšie.

3. Súčet existuje v poli

Problém: Vzhľadom na zoradené pole celých čísel musíme zistiť, či sú v ňom dve čísla, aby sa ich súčet rovnal konkrétnej hodnote.

Napríklad ak je naše vstupné pole [1, 1, 2, 3, 4, 6, 8, 9] a cieľová hodnota je 11, potom by sa mala naša metóda vrátiť pravda. Ak je však cieľová hodnota 20, malo by sa to vrátiť nepravdivé.

Najprv sa pozrime na naivné riešenie:

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

Vo vyššie uvedenom riešení sme sa slučkovali cez vstupné pole dvakrát, aby sme získali všetky možné kombinácie. Skontrolovali sme súčet kombinácie s cieľovou hodnotou a vrátili sme sa pravda ak sa zhoduje. Časová zložitosť tohto riešenia je O (n ^ 2) .

Teraz sa pozrime, ako tu môžeme použiť dvojbodovú techniku:

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

Pretože pole je už zoradené, môžeme použiť dva ukazovatele. Jeden ukazovateľ začína od začiatku poľa a druhý ukazovateľ začína od konca poľa a potom pridávame hodnoty v týchto ukazovateľoch. Ak je súčet hodnôt menší ako cieľová hodnota, zvyšujeme ľavý ukazovateľ a ak je súčet vyšší ako cieľová hodnota, znižujeme pravý ukazovateľ.

Tieto ukazovatele posúvame ďalej, kým nezískame súčet, ktorý zodpovedá cieľovej hodnote, alebo kým nedosiahneme stred poľa a nenájdeme žiadne kombinácie. Časová zložitosť tohto riešenia je O (n) a priestorová zložitosť je O (1), významné zlepšenie oproti našej prvej implementácii.

4. Otočte pole k Kroky

Problém: Pri zadanom poli otočte pole doprava o k kroky, kde k nie je negatívny. Napríklad ak je naše vstupné pole [1, 2, 3, 4, 5, 6, 7] a k je 4, potom by mal byť výstup [4, 5, 6, 7, 1, 2, 3].

Môžeme to vyriešiť tak, že budeme mať opäť dve slučky, čo nám skomplikuje čas O (n ^ 2) alebo použitím extra dočasného poľa, ale tým sa priestor skomplikuje O (n).

Vyriešme to radšej pomocou techniky dvoch ukazovateľov:

public void rotate (int [] vstup, int krok) {step% = input.length; reverzný (vstup, 0, vstupná dĺžka - 1); reverz (vstup, 0, krok - 1); reverz (vstup, krok, vstup.dĺžka - 1); } private void reverse (int [] vstup, int start, int end) {while (start <end) {int temp = input [start]; vstup [štart] = vstup [koniec]; vstup [koniec] = teplota; štart ++; koniec--; }}

Vo vyššie uvedených metódach niekoľkokrát obrátime časti vstupného poľa na miesto, aby sme dosiahli požadovaný výsledok. Na obrátenie sekcií sme použili prístup s dvoma ukazovateľmi, keď sa zámena prvkov robila na oboch koncoch sekcie poľa.

Konkrétne najskôr obrátime všetky prvky poľa. Potom otočíme prvý k prvkov, po ktorých nasleduje obrátenie zvyšku prvkov. Časová zložitosť tohto riešenia je O (n) a zložitosť priestoru je O (1).

5. Stredný prvok v a LinkedList

Problém: Uvedené jednotlivo LinkedList, nájdite jeho stredný prvok. Napríklad ak náš vstup LinkedList je 1->2->3->4->5, potom by mal byť výstup 3.

Dvojpolohovú techniku ​​môžeme použiť aj v iných dátových štruktúrach podobných poliam ako a LinkedList:

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

V tomto prístupe prechádzame prepojeným zoznamom pomocou dvoch ukazovateľov. Jeden ukazovateľ sa zvyšuje o jeden, zatiaľ čo druhý sa zvyšuje o dva. Keď rýchly ukazovateľ dosiahne koniec, pomalý ukazovateľ bude v strede prepojeného zoznamu. Časová zložitosť tohto riešenia je O (n) a priestorová zložitosť je O (1).

6. Záver

V tomto článku sme diskutovali o tom, ako môžeme použiť techniku ​​dvoch ukazovateľov, a to tým, že sme videli niekoľko príkladov, a pozreli sme sa na to, ako zvyšuje účinnosť nášho algoritmu.

Kód v tomto článku je k dispozícii na stránkach Github.


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