1. Обзор
В этом руководстве мы обсудим несколько методов в Java, как удалить повторяющиеся символы из строки.
Для каждой техники мы также кратко расскажем о ее временной и пространственной сложности.
2. Использование различных
Давайте начнем с удаления дубликатов из нашей строки, используя отдельный метод, представленный в Java 8.
Ниже мы получаем экземпляр потока Int S из заданного строкового объекта. Затем мы используем отдельный метод для удаления дубликатов. Наконец, мы вызываем метод forEach для перебора отдельных символов и добавления их в наш StringBuilder : [](/lessons/b/-java-string-builder-string-buffer)
StringBuilder sb = new StringBuilder();
str.chars().distinct().forEach(c -> sb.append((char) c));
Временная сложность: O(n) — время выполнения цикла прямо пропорционально размеру входной строки.
Вспомогательное пространство: O(n) — так как Different использует LinkedHashSet для внутреннего использования, и мы также сохраняем результирующую строку в объекте StringBuilder .
Поддерживает порядок: Да, поскольку LinkedHashSet поддерживает порядок своих элементов.
И хотя хорошо, что Java 8 так хорошо справляется с этой задачей, давайте сравним ее с усилиями по развертыванию нашей собственной.
3. Использование indexOf
Наивный подход к удалению дубликатов из строки просто включает в себя цикл по вводу и использование метода indexOf для проверки того, существует ли уже текущий символ в результирующей строке :
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);
}
}
Временная сложность: O(n * n) — для каждого символа метод indexOf просматривает оставшуюся строку.
Вспомогательное пространство: O(n) — требуется линейное пространство, так как мы используем StringBuilder для хранения результата.
Поддерживает порядок: Да
Этот метод имеет ту же пространственную сложность, что и первый подход, но работает намного медленнее.
4. Использование массива символов
Мы также можем удалить дубликаты из нашей строки, преобразовав ее в массив символов , а затем перебрав каждый символ и сравнив его со всеми последующими символами .
Как видно ниже, мы создаем два цикла for и проверяем, повторяется ли каждый элемент в строке. Если дубликат найден, мы не добавляем его в StringBuilder :
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]);
}
}
Временная сложность: O(n * n) — у нас есть внутренний и внешний цикл, которые обходят входную строку.
Вспомогательное пространство: O(n) — требуется линейное пространство, поскольку переменная chars хранит новую копию введенной строки, и мы также используем StringBuilder для сохранения результата.
Поддерживает порядок: Да
Опять же, наша вторая попытка работает плохо по сравнению с предложением Core Java, но давайте посмотрим, чего мы добьемся в нашей следующей попытке.
5. Использование сортировки
В качестве альтернативы, повторяющиеся символы можно удалить, отсортировав нашу входную строку, чтобы сгруппировать дубликаты. Для этого нам нужно преобразовать строку в массив символов и отсортировать ее с помощью метода Arrays . способ сортировки . Наконец, мы пройдемся по отсортированному массиву символов .
На каждой итерации мы будем сравнивать каждый элемент массива с предыдущим элементом. Если элементы отличаются, мы добавим текущий символ в StringBuilder:
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]);
}
}
}
Временная сложность: O (n log n) — сортировка использует быструю сортировку с двумя опорными точками , которая обеспечивает производительность O (n log n) для многих наборов данных.
Вспомогательное пространство: O(n) — поскольку метод toCharArray делает копию входной строки .
Поддерживает порядок: Нет
Давайте попробуем это снова с нашей последней попыткой.
6. Использование набора
Другой способ удалить повторяющиеся символы из строки — использовать Set . Если нас не волнует порядок символов в нашей выходной строке, мы можем использовать HashSet . В противном случае мы можем использовать LinkedHashSet для поддержания порядка вставки.
В обоих случаях мы будем перебирать входную строку и добавлять каждый символ в Set . Как только символы будут вставлены в набор, мы пройдемся по нему, чтобы добавить их в StringBuilder и вернуть результирующую строку:
StringBuilder sb = new StringBuilder();
Set<Character> linkedHashSet = new LinkedHashSet<>();
for (int i = 0; i < str.length(); i++) {
linkedHashSet.add(str.charAt(i));
}
for (Character c : linkedHashSet) {
sb.append(c);
}
Временная сложность: O(n) — время выполнения цикла прямо пропорционально размеру входной строки.
Вспомогательное пространство: O(n) – место, необходимое для набора , зависит от размера входной строки; также мы используем StringBuilder для хранения результата
Поддерживает порядок: LinkedHashSet — да, HashSet — нет
И вот мы подошли к подходу Core Java! Не слишком шокирует то, что это очень похоже на то, что уже делает Different.
7. Заключение
В этой статье мы рассмотрели несколько способов удаления повторяющихся символов из строки в Java. Мы также рассмотрели временную и пространственную сложность каждого из этих методов.
Как всегда, фрагменты кода можно найти на GitHub .