streamalism.org

1. Áttekintés

Ebben az oktatóanyagban többféle Java-technikát fogunk megvitatni az ismételt karakterek eltávolításáról egy karakterláncból.

Minden technikához röviden beszélünk az idő és a tér összetettségéről is.

2. Használata különböző

Kezdjük azzal, hogy eltávolítjuk a duplikátumokat a karakterláncunkból a különböző a Java 8-ban bevezetett módszer.

Az alábbiakban egy. Példányt kapunk IntSpatak egy adott karakterlánc objektumból. Akkor használjuk a különböző módszer a másolatok eltávolítására. Végül felhívjuk a az egyes módszer a különböző karakterek áttekintésére és a mi StringBuilder:

StringBuilder sb = új StringBuilder (); str.chars (). külön (). forEach (c -> sb.append ((char) c));

Idő összetettsége: Tovább) - a hurok futási ideje egyenesen arányos a bemeneti karakterlánc méretével

Kiegészítő tér:Tovább) - mióta különböző használja a LinkedHashSet belsőleg, és a kapott karakterláncot az a-ban is tároljuk StringBuilder tárgy

Rendet tart: Igen - mivel a LinkedHashSet fenntartja elemeinek sorrendjét

És bár nagyon jó, hogy a Java 8 ilyen szépen elvégzi ezt a feladatot helyettünk, hasonlítsuk össze a saját fejlesztésünkre tett erőfeszítésekkel.

3. Használata indexe

A duplikátumok húrból való eltávolításának naiv megközelítése egyszerűen magában foglalja hurok a bemeneten és a indexe módszer annak ellenőrzésére, hogy az aktuális karakter már létezik-e a kapott karakterláncban:

StringBuilder sb = új StringBuilder (); int idx; for (int i = 0; i <str.length (); i ++) {char c = str.charAt (i); idx = str.indexOf (c, i + 1); if (idx == -1) {sb.append (c); }} 

Idő összetettsége: O (n * n) - minden karakter esetében a indexe metódus végigfuttatja a fennmaradó karakterláncot

Kiegészítő tér:Tovább) - lineáris hely szükséges, mivel a StringBuilder hogy tárolja az eredményt

Rendet tart: Igen

Ez a módszer ugyanolyan térbonyolult, mint az első megközelítés, de sokkal lassabban teljesít.

4. Karaktertömb használata

A duplikátumokat a karakterláncunkból is eltávolíthatjuk átalakítása a-vá char tömb, majd hurok az egyes karakterek, és összehasonlítja az összes következő karaktert.

Mint alább láthatjuk, kettőt hozunk létre mert ciklusokat és ellenőrizzük, hogy minden elem megismétlődik-e a karakterláncban. Ha talál duplikátumot, akkor nem csatoljuk a StringBuilder:

char [] karakterek = str.toCharArray (); StringBuilder sb = új StringBuilder (); logikai ismételtChar; mert (int i = 0; i <karakterek.hossz; i ++) {ismételtChar = hamis; mert (int j = i + 1; j <karakterek.hossz; j ++) {if (karakterek [i] == karakterek [j]) {ismételtChar = igaz; szünet; }} if (! repeatChar) {sb.append (karakterek [i]); }} 

Idő összetettsége: O (n * n) - van egy belső és egy külső hurkunk, amelyek mind bejárják a bemeneti karakterláncot

Kiegészítő tér:Tovább) - lineáris hely szükséges, mivel karakterek változó eltárolja a karakterlánc bemenetének új példányát, és a StringBuilder hogy elmentse az eredményt

Rendet tart: Igen

A második kísérletünk ismét gyengén teljesít a Core Java kínálattal összehasonlítva, de nézzük meg, hová jutunk a következő próbálkozásunkkal.

5. A rendezés használata

Alternatív megoldásként az ismételt karakterek kiküszöbölhetők úgy, hogy a bemeneti karakterláncokat a duplikumok csoportosításához rendezik. Ehhez át kell alakítanunk a karakterláncot a-vá char array és rendezze a Tömbök.fajta módszer. Végül iterálunk a rendezés szerint char sor.

Minden iteráció során összehasonlítani fogjuk a tömb egyes elemeit az előző elemekkel. Ha az elemek eltérnek, akkor az aktuális karaktert hozzáfűzzük a StringBuilder:

StringBuilder sb = új StringBuilder (); if (! str.isEmpty ()) {char [] karakterek = str.toCharArray (); Tömbök.válogatás (karakterek); sb.append (karakterek [0]); mert (int i = 1; i <karakterek hossza; i ++) {if (karakterek [i]! = karakterek [i - 1]) {sb.append (karakterek [i]); }}}

Idő összetettsége: O (n log n) - a rendezés kettős elfordítású Quicksort-ot használ, amely O (n log n) teljesítményt kínál sok adathalmazon

Kiegészítő tér:Tovább) - mivel a toCharArray metódus másolja a bemenetet Húr

Rendet tart: Nem

Próbáljuk meg ezt még egyszer az utolsó kísérletünkkel.

6. Használja a Készlet

Az ismételt karakterek eltávolítása a karakterláncból egy másik módja az a használata Készlet. Ha nem érdekel a karaktersorozat a kimeneti karakterláncunkban, használhatjuk a HashSet.Ellenkező esetben használhatjuk a LinkedHashSet a beszúrási sorrend fenntartása érdekében.

Mindkét esetben áttekintjük a bemeneti karakterláncot, és minden karaktert hozzáadunk a Készlet. Amint a karakterek beillesztésre kerülnek a készletbe, iterálni fogunk rajta, hogy hozzáadjuk őket a StringBuilder és adja vissza a kapott karakterláncot:

StringBuilder sb = új StringBuilder (); Set linkHashSet = új LinkedHashSet (); for (int i = 0; i <str.length (); i ++) {kapcsoltHashSet.add (str.charAt (i)); } a (c karakterhez: linkedHashSet) {sb.append (c); } 

Idő összetettsége: Tovább) - a hurok futási ideje egyenesen arányos a bemeneti karakterlánc méretével

Kiegészítő tér:Tovább) - a Készlet a bemeneti karakterlánc méretétől függ; azt is használjuk StringBuilder hogy tárolja az eredményt

Rendet tart:LinkedHashSet - Igen, HashSet - Nem

És most megfeleltünk a Core Java megközelítésnek! Nem túl megdöbbentő megállapítani, hogy ez nagyon hasonlít a mihez különböző már megteszi.

7. Következtetés

Ebben a cikkben bemutattunk néhány módszert az ismételt karakterek eltávolítására a Java karakterláncaiból. Megvizsgáltuk ezen módszerek idő- és térbeli összetettségét is.

Mint mindig, a kódrészletek is megtalálhatók a GitHubon.