streamalism.org

1. Oversigt

I denne vejledning diskuterer vi flere teknikker i Java om, hvordan man fjerner gentagne tegn fra en streng.

For hver teknik, Vi taler også kort om dets tid og rumkompleksitet.

2. Brug tydelig

Lad os starte med at fjerne duplikaterne fra vores streng ved hjælp af tydelig metode introduceret i Java 8.

Nedenfor får vi en forekomst af en IntStream fra et givet strengobjekt. Derefter bruger vi tydelig metode til at fjerne duplikaterne. Endelig kalder vi for hver metode til at løbe over de forskellige tegn og tilføje dem til vores StringBuilder:

StringBuilder sb = ny StringBuilder (); str.chars (). tydelig (). forEach (c -> sb.append ((char) c));

Tidskompleksitet: På) - løbtiden er direkte proportional med størrelsen på inputstrengen

Hjælpeplads:På) - siden tydelig bruger en LinkedHashSet internt, og vi gemmer også den resulterende streng i en StringBuilder objekt

Opretholder orden: Ja - siden LinkedHashSet opretholder rækkefølgen af ​​dets elementer

Og selvom det er rart, at Java 8 gør denne opgave for os så pænt, lad os sammenligne det med bestræbelser på at rulle vores egne.

3. Brug indeks af

Den naive tilgang til at fjerne dubletter fra en streng involverer simpelthen looping over input og brug af indeks af metode til at kontrollere, om det aktuelle tegn allerede findes i den resulterende streng:

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

Tidskompleksitet: O (n * n) - for hvert tegn, indeks af metode løber gennem den resterende streng

Hjælpeplads:På) - Der kræves lineært rum, da vi bruger StringBuilder for at gemme resultatet

Opretholder orden: Ja

Denne metode har samme rumkompleksitet som den første tilgang, men fungerer meget langsommere.

4. Brug af et tegnarray

Vi kan også fjerne dubletter fra vores streng ved konvertere det til en char array og derefter sløjfe over hvert tegn og sammenligne det med alle efterfølgende tegn.

Som vi kan se nedenfor, opretter vi to til sløjfer, og vi kontrollerer, om hvert element gentages i strengen. Hvis der findes en duplikat, føjer vi den ikke til StringBuilder:

char [] tegn = str.toCharArray (); StringBuilder sb = ny StringBuilder (); gentaget boolskChar; for (int i = 0; i <chars.length; i ++) {repeatChar = false; for (int j = i + 1; j <tegn.længde; j ++) {hvis (tegn [i] == tegn [j]) {gentagetChar = sand; pause; }} hvis (! repeatChar) {sb.append (tegn [i]); }} 

Tidskompleksitet: O (n * n) - vi har en indre og en ydre sløjfe, der begge krydser inputstrengen

Hjælpeplads:På) - der kræves lineært rum, da tegn variabel gemmer en ny kopi af strenginput, og vi bruger også StringBuilder for at gemme resultatet

Opretholder orden: Ja

Igen fungerer vores andet forsøg dårligt sammenlignet med Core Java-tilbudet, men lad os se, hvor vi kommer med vores næste forsøg.

5. Brug af sortering

Alternativt kan gentagne tegn elimineres ved at sortere vores inputstreng til gruppedubletter. For at gøre det skal vi konvertere strengen til en char enstråle og sortere det ved hjælp af Arrays.sortere metode. Endelig gentager vi det sorterede char array.

Under hver iteration skal vi sammenligne hvert element i arrayet med det forrige element. Hvis elementerne er forskellige, føjer vi det aktuelle tegn til StringBuilder:

StringBuilder sb = ny StringBuilder (); hvis (! str.isEmpty ()) {char [] tegn = str.toCharArray (); Arrays.sort (tegn); sb.append (tegn [0]); for (int i = 1; i <chars.length; i ++) {if (tegn [i]! = tegn [i - 1]) {sb.append (tegn [i]); }}}

Tidskompleksitet: O (n log n) - sorteringen bruger et dual-pivot Quicksort, der tilbyder O (n log n) ydeevne på mange datasæt

Hjælpeplads:På) - siden toCharArray metode laver en kopi af inputet Snor

Opretholder orden: Ingen

Lad os prøve det igen med vores sidste forsøg.

6. Brug af en Sæt

En anden måde at fjerne gentagne tegn fra en streng er ved hjælp af en Sæt. Hvis vi ikke er ligeglade med rækkefølgen af ​​tegn i vores outputstreng, kan vi bruge en HashSet.Ellers kan vi bruge en LinkedHashSet for at opretholde indsættelsesordren.

I begge tilfælde løber vi over inputstrengen og tilføjer hvert tegn til Sæt. Når tegnene er indsat i sættet, gentager vi det for at tilføje dem til StringBuilder og returner den resulterende streng:

StringBuilder sb = ny StringBuilder (); Indstil linkedHashSet = ny LinkedHashSet (); for (int i = 0; i <str.length (); i ++) {linkedHashSet.add (str.charAt (i)); } for (Tegn c: linkedHashSet) {sb.append (c); } 

Tidskompleksitet: På) - runtime af sløjfen er direkte proportional med størrelsen på inputstrengen

Hjælpeplads:På) - krævet plads til Sæt afhænger af størrelsen på inputstrengen; også bruger vi StringBuilder for at gemme resultatet

Opretholder orden:LinkedHashSet - Ja, HashSet - Nej

Og nu har vi matchet Core Java-tilgangen! Det er ikke særlig chokerende at finde ud af, at dette ligner meget hvad tydelig gør det allerede.

7. Konklusion

I denne artikel dækkede vi et par måder at fjerne gentagne tegn fra en streng i Java. Vi så også på tid og rumkompleksitet for hver af disse metoder.

Som altid kan kodeuddrag findes på GitHub.