1. Übersicht
In diesem Tutorial werden verschiedene Techniken in Java zum Entfernen wiederholter Zeichen aus einer Zeichenfolge erläutert.
Für jede Technik werden wir auch kurz auf ihre zeitliche und räumliche Komplexität eingehen.
2. Verwenden Sie verschiedene
Beginnen wir damit , die Duplikate aus unserer String Entfernen der Verwendung verschiedene Verfahren in Java 8 eingeführt.
Unten erhalten wir eine Instanz eines Int S- Treams von einem bestimmten String-Objekt. Dann verwenden wir die eindeutige Methode, um die Duplikate zu entfernen. Schließlich rufen wir die forEach- Methode auf, um die verschiedenen Zeichen zu durchlaufen und sie an unseren StringBuilder anzuhängen :
StringBuilder sb = new StringBuilder(); str.chars().distinct().forEach(c -> sb.append((char) c));Zeitkomplexität: O (n) - Die Laufzeit der Schleife ist direkt proportional zur Größe der Eingabezeichenfolge
Hilfsraum: O (n) - da unterschiedliche Anwendungen ein LinkedHashSet intern und wir auch den resultierenden String in einem Speicherstring Objekt
Ordnet die Reihenfolge an : Ja - da das LinkedHashSet die Reihenfolge seiner Elemente beibehält
Und obwohl es schön ist, dass Java 8 diese Aufgabe so gut für uns erledigt, vergleichen wir sie mit den Bemühungen, unsere eigenen zu rollen.
3. Verwenden von indexOf
Der naive Ansatz zum Entfernen von Duplikaten aus einer Zeichenfolge besteht einfach darin, die Eingabe zu durchlaufen und mithilfe der indexOf- Methode zu überprüfen, ob das aktuelle Zeichen bereits in der resultierenden Zeichenfolge vorhanden ist :
StringBuilder sb = new 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); } } Zeitkomplexität: O (n * n) - Für jedes Zeichen durchläuft die indexOf- Methode die verbleibende Zeichenfolge
Hilfsraum: O (n) - linearer Raum ist erforderlich, da wir den StringBuilder zum Speichern des Ergebnisses verwenden
Aufrechterhaltung der Ordnung: Ja
Diese Methode hat die gleiche räumliche Komplexität wie der erste Ansatz, arbeitet jedoch viel langsamer.
4. Verwenden eines Zeichenarrays
Wir können auch Duplikate aus unserer Zeichenfolge entfernen, indem wir sie in ein char- Array konvertieren, dann jedes Zeichen durchlaufen und es mit allen nachfolgenden Zeichen vergleichen .
Wie wir unten sehen können, erstellen wir zwei for- Schleifen und prüfen, ob jedes Element in der Zeichenfolge wiederholt wird. Wenn ein Duplikat gefunden wird, hängen wir es nicht an den StringBuilder an :
char[] chars = str.toCharArray(); StringBuilder sb = new StringBuilder(); boolean repeatedChar; for (int i = 0; i < chars.length; i++) { repeatedChar = false; for (int j = i + 1; j < chars.length; j++) { if (chars[i] == chars[j]) { repeatedChar = true; break; } } if (!repeatedChar) { sb.append(chars[i]); } } Zeitkomplexität: O (n * n) - Wir haben eine innere und eine äußere Schleife, die beide die Eingabezeichenfolge durchlaufen
Hilfsraum: O (n) - linearer Raum ist erforderlich, da die Variable chars eine neue Kopie der Zeichenfolgeneingabe speichert und wir auch den StringBuilder verwenden , um das Ergebnis zu speichern
Aufrechterhaltung der Ordnung: Ja
Auch hier ist unser zweiter Versuch im Vergleich zum Core Java-Angebot schlecht, aber lassen Sie uns sehen, wo wir bei unserem nächsten Versuch hinkommen.
5. Verwenden der Sortierung
Alternativ können wiederholte Zeichen eliminiert werden, indem unsere Eingabezeichenfolge nach Gruppenduplikaten sortiert wird. Dazu müssen wir den String in ein Zeichen konvertieren und ihn mit den Arrays sortieren . Sortierverfahren . Schließlich werden wir über das sortierte char- Array iterieren .
Während jeder Iteration werden wir jedes Element des Arrays mit dem vorherigen Element vergleichen. Wenn die Elemente unterschiedlich sind, hängen wir das aktuelle Zeichen an den StringBuilder an:
StringBuilder sb = new StringBuilder(); if(!str.isEmpty()) { char[] chars = str.toCharArray(); Arrays.sort(chars); sb.append(chars[0]); for (int i = 1; i < chars.length; i++) { if (chars[i] != chars[i - 1]) { sb.append(chars[i]); } } }Zeitkomplexität: O (n log n) - Die Sortierung verwendet einen Quicksort mit zwei Pivots, der für viele Datensätze eine O (n log n) -Leistung bietet
Hilfsraum: O (n) - seit der ToCharArray Methode erstellt eine Kopie des Eingang String
Aufrechterhaltung der Reihenfolge: Nein
Versuchen wir das noch einmal mit unserem letzten Versuch.
6. Verwenden eines Sets
Eine andere Möglichkeit, wiederholte Zeichen aus einer Zeichenfolge zu entfernen, ist die Verwendung eines Sets . Wenn uns die Reihenfolge der Zeichen in unserer Ausgabezeichenfolge nicht wichtig ist, können wir ein HashSet verwenden . Andernfalls können wir ein LinkedHashSet verwenden , um die Einfügereihenfolge beizubehalten.
In beiden Fällen durchlaufen wir die Eingabezeichenfolge und fügen jedes Zeichen dem Set hinzu . Sobald die Zeichen in den Satz eingefügt wurden, werden wir sie durchlaufen, um sie dem StringBuilder hinzuzufügen und den resultierenden String zurückzugeben:
StringBuilder sb = new StringBuilder(); Set linkedHashSet = new LinkedHashSet(); for (int i = 0; i < str.length(); i++) { linkedHashSet.add(str.charAt(i)); } for (Character c : linkedHashSet) { sb.append(c); } Zeitkomplexität: O (n) - Die Laufzeit der Schleife ist direkt proportional zur Größe der Eingabezeichenfolge
Hilfsraum: O (n) - Der für das Set erforderliche Platz hängt von der Größe der Eingabezeichenfolge ab. Außerdem verwenden wir den StringBuilder , um das Ergebnis zu speichern
Aufrechterhaltung der Reihenfolge: LinkedHashSet - Ja, HashSet - Nein
Und jetzt haben wir den Core Java-Ansatz angepasst! Es ist nicht sehr schockierend herauszufinden, dass dies dem sehr ähnlich ist, was Different bereits tut.
7. Fazit
In diesem Artikel haben wir einige Möglichkeiten behandelt, um wiederholte Zeichen aus einer Zeichenfolge in Java zu entfernen. Wir haben uns auch mit der zeitlichen und räumlichen Komplexität jeder dieser Methoden befasst.
Wie immer finden Sie Code-Schnipsel auf GitHub.