streamalism.org

1. Oversikt

I denne opplæringen vil vi diskutere flere teknikker i Java om hvordan du fjerner gjentatte tegn fra en streng.

For hver teknikk, vi vil også snakke kort om tid og romkompleksitet.

2. Bruke distinkt

La oss starte med å fjerne duplikatene fra strengen vår ved hjelp av distinkt metoden introdusert i Java 8.

Nedenfor får vi en forekomst av en IntStream fra et gitt strengobjekt. Så bruker vi distinkt metode for å fjerne duplikatene. Til slutt kaller vi for hver metode for å løkke over de forskjellige tegnene og legge dem til vår StringBuilder:

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

Tidskompleksitet: På) - kjøretiden til sløyfen er direkte proporsjonal med størrelsen på inngangsstrengen

Hjelpeplass:På) - siden distinkt bruker en LinkedHashSet internt, og vi lagrer også den resulterende strengen i en StringBuilder gjenstand

Opprettholder orden: Ja - siden LinkedHashSet opprettholder rekkefølgen av elementene

Og selv om det er hyggelig at Java 8 gjør denne oppgaven for oss så pent, la oss sammenligne den med innsatsen for å rulle vår egen.

3. Bruke oversikt over

Den naive tilnærmingen til å fjerne duplikater fra en streng innebærer ganske enkelt sløyfer over inngangen og bruker oversikt over metode for å sjekke om det nåværende tegnet allerede eksisterer i den resulterende strengen:

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.tillegg (c); }} 

Tidskompleksitet: O (n * n) - for hver karakter, oversikt over metoden går gjennom den gjenværende strengen

Hjelpeplass:På) - Det kreves lineær plass siden vi bruker StringBuilder for å lagre resultatet

Opprettholder orden: Ja

Denne metoden har samme romkompleksitet som den første tilnærmingen, men utfører mye tregere.

4. Bruke en tegneserie

Vi kan også fjerne duplikater fra strengen vår konvertere den til en røye array og deretter sløyfe over hvert tegn og sammenligne det med alle påfølgende tegn.

Som vi kan se nedenfor, lager vi to til sløyfer og vi sjekker om hvert element blir gjentatt i strengen. Hvis det finnes en duplikat, legger vi den ikke til StringBuilder:

char [] tegn = str.toCharArray (); StringBuilder sb = ny StringBuilder (); gjentatt boolskChar; for (int i = 0; i <chars.length; i ++) {gjentattChar = false; for (int j = i + 1; j <chars.length; j ++) {if (chars [i] == chars [j]) {repeatChar = true; gå i stykker; }} hvis (! repeatChar) {sb.append (tegn [i]); }} 

Tidskompleksitet: O (n * n) - vi har en indre og en ytre sløyfe som begge krysser inngangsstrengen

Hjelpeplass:På) - det kreves lineært rom siden tegn variabel lagrer en ny kopi av strenginngangen, og vi bruker også StringBuilder for å lagre resultatet

Opprettholder orden: Ja

Igjen, vårt andre forsøk fungerer dårlig sammenlignet med Core Java-tilbudet, men la oss se hvor vi kommer med vårt neste forsøk.

5. Bruke sortering

Alternativt kan gjentatte tegn elimineres ved å sortere inngangsstrengen vår for å gruppere duplikater. For å gjøre det, må vi konvertere strengen til a røye astråle og sortere den ved hjelp av Arrays.sortere metode. Til slutt vil vi gjenta det sorterte røye array.

Under hver iterasjon skal vi sammenligne hvert element i matrisen med det forrige elementet. Hvis elementene er forskjellige, legger vi gjeldende karakter 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 (chars [i]! = chars [i - 1]) {sb.append (chars [i]); }}}

Tidskompleksitet: O (n log n) - sorten bruker en dual-pivot Quicksort som tilbyr O (n log n) ytelse på mange datasett

Hjelpeplass:På) - siden toCharArray metoden lager en kopi av inngangen String

Opprettholder orden: Nei

La oss prøve det igjen med vårt siste forsøk.

6. Bruke en Sett

En annen måte å fjerne gjentatte tegn fra en streng er ved bruk av a Sett. Hvis vi ikke bryr oss om rekkefølgen av tegn i utgangsstrengen vår, kan vi bruke en HashSet.Ellers kan vi bruke en LinkedHashSet for å opprettholde innsettingsordren.

I begge tilfeller slår vi over inngangsstrengen og legger til hvert tegn i Sett. Når tegnene er satt inn i settet, vil vi gjenta det for å legge dem til StringBuilder og returner den resulterende strengen:

StringBuilder sb = ny StringBuilder (); Sett 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å) - kjøretiden til sløyfen er direkte proporsjonal med størrelsen på inngangsstrengen

Hjelpeplass:På) - nødvendig plass til Sett avhenger av størrelsen på inngangsstrengen; også bruker vi StringBuilder for å lagre resultatet

Opprettholder orden:LinkedHashSet - Ja, HashSet - Nei

Og nå har vi matchet Core Java-tilnærmingen! Det er ikke veldig sjokkerende å finne ut at dette ligner veldig på hva distinkt gjør det allerede.

7. Konklusjon

I denne artikkelen tok vi for oss noen måter å fjerne gjentatte tegn fra en streng i Java. Vi så også på tid og romkompleksitet til hver av disse metodene.

Som alltid kan du finne kodebiter på GitHub.