streamalism.org

1. Áttekintés

Ebben az oktatóanyagban a tömbökkel és listákkal kapcsolatos problémák megoldásának kétpontos megközelítését tárgyaljuk. Ez a technika egyszerű és hatékony módszer algoritmusunk teljesítményének javítására.

2. A technika leírása

Számos tömböt vagy listát érintő problémában elemeznünk kell a tömb minden egyes elemét a többi eleméhez képest.

Az ilyen problémák megoldásához általában az első indexből indulunk ki, és a megvalósítás függvényében egy vagy több alkalommal végigvezetünk a tömbön. Néha ideiglenes tömböt is létre kell hoznunk a problémánk követelményeitől függően.

A fenti megközelítés megadhatja számunkra a helyes eredményt, de valószínűleg nem a leginkább hely- és időhatékony megoldást nyújtja.

Ennek eredményeként gyakran jó megfontolni, hogy problémánk hatékonyan megoldható-e a kétmutatós megközelítés.

A kétmutatós megközelítésben a mutatók egy tömb indexeire utalnak. Mutatók használatával ciklusonként két elemet dolgozhatunk fel, egy helyett.

A kétmutatós megközelítés közös mintái:

• Két mutató az elejétől a végéig, mindkettő találkozásáig
• Az egyik mutató lassú, míg a másik mutató gyorsabban halad

Mindkét fenti minta segíthet a idő és tér összetettsége problémáinkból, mivel kevesebb ismétléssel és túl sok további hely használata nélkül érjük el a várt eredményt.

Most nézzünk meg néhány példát, amelyek segítenek megérteni ezt a technikát egy kicsit jobban.

3. Az összeg egy tömbben létezik

Probléma: Az egész számok rendezett tömbje alapján meg kell látnunk, van-e benne két szám úgy, hogy összegük megegyezzen egy adott értékkel.

Például, ha a bemeneti tömbünk [1, 1, 2, 3, 4, 6, 8, 9] és a célérték az 11, akkor a módszerünknek vissza kell térnie igaz. Ha azonban a célérték az 20, vissza kell térnie hamis.

Lássuk először egy naiv megoldást:

public boolean 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; }}} return false; }

A fenti megoldásban kétszer hurkoltuk a bemeneti tömböt, hogy minden lehetséges kombinációt megkapjunk. Ellenőriztük a kombináció összegét a célértékkel és visszatértünk igaz ha egyezik. A megoldás időbeli összetettsége O (n ^ 2) .

Most nézzük meg, hogyan alkalmazhatjuk itt a kétpontos technikát:

nyilvános logikai kettőSum (int [] input, int targetValue) {int pointerOne = 0; int pointerTwo = bemenet.hossz - 1; while (pointerOne <pointerTwo) {int összeg = bemenet [pointerOne] + bemenet [pointerTwo]; if (összeg == célérték) {return true; } else if (összeg <célérték) {pointerOne ++; } else {pointerTwo--; }} return false; }

Mivel a tömb már rendezve van, két mutatót használhatunk. Az egyik mutató a tömb elejéről indul, a másik mutató a tömb végéről indul, majd ezekhez a mutatókhoz adjuk hozzá az értékeket. Ha az értékek összege kisebb, mint a célérték, akkor növeljük a bal mutatót, és ha az összeg magasabb, mint a célérték, akkor a jobb mutatót csökkentjük.

Addig mozgatjuk ezeket a mutatókat, amíg meg nem kapjuk a célértéknek megfelelő összeget, vagy el nem érjük a tömb közepét, és nem találtunk kombinációt. A megoldás időbeli összetettsége Tovább) az űr komplexitása pedig az O (1), jelentős előrelépés az első megvalósításhoz képest.

4. Forgassa el a tömböt k Lépések

Probléma: Adott tömb, forgassa jobbra a tömböt k lépések, hol k nem negatív. Például, ha a bemeneti tömbünk [1, 2, 3, 4, 5, 6, 7] és k van 4, akkor a kimenet legyen [4, 5, 6, 7, 1, 2, 3].

Megoldhatjuk ezt úgy, hogy ismét két hurok van, ami megnehezíti az időt O (n ^ 2) vagy egy extra, ideiglenes tömb használatával, de ez megnehezíti a helyet Tovább).

Megoldjuk ezt inkább a két mutató technikával:

public void rotate (int [] input, int step) {lépés% = bemenet.hossz; hátramenet (bemenet, 0, bemenet.hossz - 1); hátramenet (bemenet, 0, 1. lépés); hátramenet (bemenet, lépés, bemenet.hossz - 1); } private void reverse (int [] input, int start, int end) {while (start <end) {int temp = input [start]; input [kezdet] = input [vég]; bemenet [vég] = hőmérséklet; start ++; vége--; }}

A fenti módszerekben a bemeneti tömb szakaszait többször megfordítjuk a helyén, többször is, hogy megkapjuk a kívánt eredményt. A szakaszok megfordításához a kétpontos megközelítést alkalmaztuk, ahol az elemek cseréjét a tömb szakasz mindkét végén végeztük.

Pontosabban először a tömb összes elemét megfordítjuk. Ezután megfordítjuk az elsőt k elemek, majd a többi elem megfordítása. A megoldás időbeli összetettsége Tovább) és a tér bonyolultsága az O (1).

5. Középső elem a LinkedList

Probléma: Egyenként adva LinkedList, keresse meg középső elemét. Például, ha a bemenetünk LinkedList van 1->2->3->4->5, akkor a kimenet legyen 3.

A kétpontos technikát más adatstruktúrákban is alkalmazhatjuk, hasonlóan az a tömbökhöz LinkedList:

public T findMiddle (MyNode fej) {MyNode slowPointer = fej; MyNode fastPointer = fej; míg (fastPointer.next! = null && fastPointer.next.next! = null) {fastPointer = fastPointer.next.next; slowPointer = slowPointer.next; } return slowPointer.data; }

Ebben a megközelítésben két mutató segítségével haladunk át a linkelt listán. Az egyik mutatót egy, a másikat kettővel növeljük. Amikor a gyors mutató a végére ér, a lassú mutató a csatolt lista közepén lesz. A megoldás időbeli összetettsége Tovább) , és az űr bonyolultsága az O (1).

6. Következtetés

Ebben a cikkben megvitattuk, hogyan alkalmazhatnánk a kétmutatós technikát néhány példával, és megvizsgáltuk, hogyan javítja az algoritmusunk hatékonyságát.

A cikk kódja a Github oldalon érhető el.