streamalism.org

1. Pregled

U ovom uputstvu raspravit ćemo o dvostrukom pristupu za rješavanje problema koji uključuju nizove i popise. Ova je tehnika jednostavan i učinkovit način za poboljšanje izvedbe našeg algoritma.

2. Opis tehnike

U mnogim problemima koji uključuju nizove ili popise, moramo analizirati svaki element niza u usporedbi s ostalim elementima.

Da bismo riješili probleme poput ovih, obično započinjemo od prvog indeksa i petlju prolazimo kroz niz jedan ili više puta, ovisno o našoj implementaciji. Ponekad moramo stvoriti i privremeni niz, ovisno o zahtjevima našeg problema.

Gore navedeni pristup mogao bi nam dati točan rezultat, ali vjerojatno nam neće pružiti prostorno i vremenski najučinkovitije rješenje.

Kao rezultat toga, često je dobro razmisliti može li se naš problem učinkovito riješiti uporabom dvostruki pristup.

U pristupu s dva pokazivača, pokazivači se odnose na indekse niza. Korištenjem pokazivača možemo obraditi dva elementa po petlji, umjesto samo jednog.

Uobičajeni obrasci u dvostrukom pristupu uključuju:

• Po dva pokazivača, počevši od početka i do kraja, dok se oboje ne sretnu
• Jedan se pokazivač kreće sporim tempom, dok se drugi pokazivač kreće bržim tempom

Oba navedena uzorka mogu nam pomoći da smanjimo složenost vremena i prostora naših problema jer dobivamo očekivani rezultat u manje ponavljanja i bez korištenja previše dodatnog prostora.

Pogledajmo sada nekoliko primjera koji će nam pomoći da malo bolje razumijemo ovu tehniku.

3. Zbir postoji u nizu

Problem: S obzirom na razvrstani niz cijelih brojeva, moramo vidjeti postoje li u njemu dva broja takva da je njihov zbroj jednak određenoj vrijednosti.

Na primjer, ako je naš ulazni niz [1, 1, 2, 3, 4, 6, 8, 9] a ciljana vrijednost je 11, tada bi se naša metoda trebala vratiti pravi. Međutim, ako je ciljana vrijednost 20, trebalo bi se vratiti lažno.

Prvo da vidimo naivno rješenje:

javna logička vrijednost twoSumSlow (int [] input, int targetValue) {for (int i = 0; i <input.length; i ++) {for (int j = 1; j <input.length; j ++) {if (input [i ] + ulaz [j] == targetValue) {return true; }}} return false; }

U gore navedenom rješenju dva smo puta pregledali ulazni niz da bismo dobili sve moguće kombinacije. Provjerili smo zbroj kombinacija prema ciljanoj vrijednosti i vratili pravi ako se podudara. Vremenska složenost ovog rješenja je O (n ^ 2) .

Sada da vidimo kako ovdje možemo primijeniti tehniku ​​s dva pokazivača:

javna logička vrijednost 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; } inače if (sum <targetValue) {pointerOne ++; } else {pointerTwo--; }} return false; }

Budući da je niz već sortiran, možemo koristiti dva pokazivača. Jedan pokazivač započinje s početka polja, a drugi pokazivač s kraja niza, a zatim zbrajamo vrijednosti na tim pokazivačima. Ako je zbroj vrijednosti manji od ciljne vrijednosti, povećavamo lijevi pokazivač, a ako je zbroj veći od ciljne vrijednosti, smanjujemo desni pokazivač.

Nastavljamo s pomicanjem ovih pokazivača sve dok ne dobijemo zbroj koji se podudara s ciljanom vrijednošću ili dok ne dosegnemo sredinu polja, a kombinacije nisu pronađene. Vremenska složenost ovog rješenja je Na) a složenost prostora je O (1), značajan napredak u odnosu na našu prvu implementaciju.

4. Rotirajte polje k Koraci

Problem: S obzirom na niz, zakrenite niz udesno za k koraci, gdje k nije negativan. Na primjer, ako je naš ulazni niz [1, 2, 3, 4, 5, 6, 7] i k je 4, tada bi izlaz trebao biti [4, 5, 6, 7, 1, 2, 3].

To možemo riješiti ponovnim postojanjem dvije petlje što će vrijeme učiniti složenim O (n ^ 2) ili upotrebom dodatnog, privremenog niza, ali to će prostor učiniti složenim Na).

Riješimo to pomoću dvostruke tehnike:

rotiranje javne praznine (int [] ulaz, int korak) {korak% = input.length; obrnuto (input, 0, input.length - 1); obrnuto (ulaz, 0, korak - 1); obrnuto (input, step, input.length - 1); } private void reverse (int [] input, int start, int end) {while (start <end) {int temp = input [start]; ulaz [početak] = ulaz [kraj]; ulaz [kraj] = temp; start ++; kraj--; }}

U gornjim metodama, više puta preokrećemo odjeljke ulaznog niza na mjestu da bismo dobili traženi rezultat. Za preokretanje sekcija koristili smo pristup s dva pokazivača gdje je zamjena elemenata izvršena na oba kraja odjeljka niza.

Konkretno, prvo preokrećemo sve elemente niza. Zatim, obrnemo prvu k elementi praćeni preokretanjem ostalih elemenata. Vremenska složenost ovog rješenja je Na) i složenost prostora je O (1).

5. Srednji element u a LinkedList

Problem: Daje se pojedinačno LinkedList, pronađite njegov srednji element. Na primjer, ako je naš unos LinkedList je 1->2->3->4->5, tada bi izlaz trebao biti 3.

Tehniku ​​dvostrukih pokazivača možemo koristiti i u drugim strukturama podataka sličnim nizovima poput LinkedList:

javni T findMiddle (glava MyNode) {MyNode slowPointer = head; MyNode fastPointer = glava; dok (fastPointer.next! = null && fastPointer.next.next! = null) {fastPointer = fastPointer.next.next; slowPointer = slowPointer.next; } return slowPointer.data; }

U ovom pristupu prelazimo povezani popis koristeći dva pokazivača. Jedan se pokazivač povećava za jedan, dok se drugi povećava za dva. Kada brzi pokazivač dođe do kraja, spori će se nalaziti na sredini povezanog popisa. Vremenska složenost ovog rješenja je Na) , a složenost prostora je O (1).

6. Zaključak

U ovom smo članku razgovarali o tome kako možemo primijeniti tehniku ​​s dva pokazivača vidjevši neke primjere i pogledali kako poboljšava učinkovitost našeg algoritma.

Kôd u ovom članku dostupan je na Githubu.