streamalism.org

1. Overzicht

In deze tutorial bespreken we verschillende technieken in Java om herhaalde tekens uit een string te verwijderen.

Voor elke techniek we zullen ook kort praten over de complexiteit van tijd en ruimte.

2. Met behulp van onderscheiden

Laten we beginnen met het verwijderen van de duplicaten uit onze string met behulp van de onderscheiden methode geïntroduceerd in Java 8.

Hieronder krijgen we een exemplaar van een IntStream van een bepaald stringobject. Vervolgens gebruiken we de onderscheiden methode om de duplicaten te verwijderen. Ten slotte noemen we de voor elk methode om over de verschillende karakters heen te lopen en ze toe te voegen aan onze StringBuilder:

StringBuilder sb = nieuwe StringBuilder (); str.chars (). distinct (). forEach (c -> sb.append ((char) c));

Tijdscomplexiteit: Aan) - looptijd van de lus is recht evenredig met de grootte van de invoertekenreeks

Extra ruimte:Aan) - sinds onderscheiden gebruikt een LinkedHashSet intern en we slaan de resulterende string ook op in een StringBuilder voorwerp

Handhaaft Orde: Ja - sinds de LinkedHashSet handhaaft de volgorde van zijn elementen

En hoewel het leuk is dat Java 8 deze taak zo goed voor ons doet, laten we het vergelijken met de inspanningen om onze eigen taak uit te voeren.

3. Met behulp van index van

De naïeve benadering om duplicaten uit een string te verwijderen, houdt simpelweg in loop over de ingang en gebruik de index van methode om te controleren of het huidige teken al bestaat in de resulterende string:

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

Tijdscomplexiteit: O (n * n) - voor elk teken, de index van methode loopt door de resterende string

Extra ruimte:Aan) - lineaire ruimte is vereist omdat we de StringBuilder om het resultaat op te slaan

Handhaaft Orde: Ja

Deze methode heeft dezelfde ruimtecomplexiteit als de eerste benadering, maar presteert veel langzamer.

4. Met behulp van een Character Array

We kunnen ook duplicaten uit onze string verwijderen door omzetten in een char array en vervolgens elk teken doorlopen en het vergelijken met alle volgende tekens.

Zoals we hieronder kunnen zien, maken we er twee voor loops en we controleren of elk element in de string wordt herhaald. Als er een duplicaat wordt gevonden, voegen we dit niet toe aan het StringBuilder:

char [] chars = str.toCharArray (); StringBuilder sb = nieuwe StringBuilder (); boolean herhaaldChar; for (int i = 0; i <chars.length; i ++) {repeatChar = false; for (int j = i + 1; j <chars.length; j ++) {if (chars [i] == chars [j]) {repeatChar = true; breken; }} if (! repeatChar) {sb.append (chars [i]); }} 

Tijdscomplexiteit: O (n * n) - we hebben een binnenste en een buitenste lus die beide de invoerstring doorkruisen

Extra ruimte:Aan) - lineaire ruimte is vereist aangezien de tekens variabele slaat een nieuwe kopie van de stringinvoer op en we gebruiken ook de StringBuilder om het resultaat op te slaan

Behoudt orde: Ja

Nogmaals, onze tweede poging presteert slecht in vergelijking met het Core Java-aanbod, maar laten we eens kijken waar we komen met onze volgende poging.

5. Sorteren gebruiken

Als alternatief kunnen herhaalde tekens worden geëlimineerd door onze invoerstring te sorteren om duplicaten te groeperen. Om dat te doen, moeten we de string converteren naar een char eenrray en sorteer het met de Arrays.soort methode. Ten slotte zullen we de gesorteerde char array.

Tijdens elke iteratie gaan we elk element van de array vergelijken met het vorige element. Als de elementen anders zijn, voegen we het huidige teken toe aan de StringBuilder:

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

Tijdscomplexiteit: O (n log n) - de sort maakt gebruik van een dual-pivot Quicksort die O (n log n) -prestaties biedt op veel gegevenssets

Extra ruimte:Aan) - sinds de toCharArray methode maakt een kopie van de invoer Draad

Behoudt orde: Nee

Laten we dat nog eens proberen met onze laatste poging.

6. Met behulp van een Set

Een andere manier om herhaalde tekens uit een string te verwijderen, is door een Set. Als het ons niet uitmaakt wat de volgorde van de tekens in onze uitvoerstring is, kunnen we een HashSet.Anders kunnen we een LinkedHashSet om de invoegvolgorde te behouden.

In beide gevallen zullen we de invoertekenreeks doorlopen en elk teken aan de Set. Zodra de tekens in de set zijn ingevoegd, zullen we deze herhalen om ze toe te voegen aan de StringBuilder en retourneer de resulterende string:

StringBuilder sb = nieuwe StringBuilder (); Set linkedHashSet = nieuwe LinkedHashSet (); voor (int i = 0; i <str.length (); i ++) {linkedHashSet.add (str.charAt (i)); } for (Character c: linkedHashSet) {sb.append (c); } 

Tijdscomplexiteit: Aan) - looptijd van de lus is recht evenredig met de grootte van de invoertekenreeks

Extra ruimte:Aan) - benodigde ruimte voor de Set hangt af van de grootte van de invoerstring; we gebruiken ook de StringBuilder om het resultaat op te slaan

Behoudt orde:LinkedHashSet - Ja, HashSet - Nee

En nu hebben we de Core Java-aanpak geëvenaard! Het is niet erg schokkend om te ontdekken dat dit erg lijkt op wat onderscheiden doet het al.

7. Conclusie

In dit artikel hebben we een aantal manieren besproken om herhaalde tekens uit een tekenreeks in Java te verwijderen. We hebben ook gekeken naar de tijd- en ruimtecomplexiteit van elk van deze methoden.

Zoals altijd zijn codefragmenten te vinden op GitHub.