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.