1. Общ преглед
В този урок ще обсъдим няколко техники в Java за това как да премахнете повтарящи се символи от низ.
За всяка техника също ще говорим накратко за нейната сложност във времето и пространството.
2. Използване на различен
Нека започнем с премахването на дубликатите от нашия низ, като използваме отделния метод, въведен в Java 8.
По-долу получаваме екземпляр на Int S трейм от даден низ обект. След това използваме отделния метод за премахване на дубликатите. И накрая, извикваме метода forEach , за да преминем през отделните символи и да ги добавим към нашия StringBuilder :
StringBuilder sb = new StringBuilder(); str.chars().distinct().forEach(c -> sb.append((char) c));Сложност във времето: O (n) - времето на изпълнение на цикъла е право пропорционално на размера на входния низ
Спомагателно пространство: O (n) - тъй като отделно използва 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. Използване на символен масив
Можем също така да премахнете дубликати от нашата поредица от превръщане в знак масив и след това цикъл с всеки знак и го сравнява с всички последващи символи .
Както виждаме по-долу, ние създаваме две за цикли и проверяваме дали всеки елемент се повтаря в низа. Ако се намери дубликат, не го добавяме към 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. Използване на сортиране
Алтернативно, повтарящите се символи могат да бъдат премахнати чрез сортиране на нашия входен низ, за да групира дубликати. За да направим това, трябва да преобразуваме низа в char a масив и да го сортираме с помощта на масивите . метод на сортиране . Накрая ще повторим сортирания масив char .
По време на всяка итерация ще сравняваме всеки елемент от масива с предишния елемент. Ако елементите са различни, ние ще добавим текущия знак към 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) - сортирането използва двойна ос Quicksort, която предлага O (n log n) производителност на много набори от данни
Спомагателно пространство: O (n) - тъй като методът toCharArray прави копие на входния низ
Поддържа поръчка: №
Нека опитаме това отново с последния ни опит.
6. Използване на комплект
Друг начин за премахване на повтарящи се символи от низ е чрез използването на Set . Ако не ни интересува реда на символите в нашия изходен низ, можем да използваме HashSet . В противен случай можем да използваме LinkedHashSet, за да поддържаме реда за вмъкване.
И в двата случая ще преминем през входния низ и ще добавим всеки знак към Set . След като символите бъдат вмъкнати в набора, ще го повторим, за да ги добавим към StringBuilder и да върнем получения низ:
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); } Сложност във времето: O (n) - времето на изпълнение на цикъла е право пропорционално на размера на входния низ
Спомагателно пространство: O (n) - пространството, необходимо за набора, зависи от размера на входния низ; също така използваме StringBuilder за съхраняване на резултата
Поддържа поръчка: LinkedHashSet - Да, HashSet - Не
И сега, ние сме подбрали подхода на Core Java! Не е много шокиращо да се установи, че това е много подобно на това, което вече прави различен .
7. Заключение
В тази статия разгледахме няколко начина за премахване на повтарящи се символи от низ в Java. Също така разгледахме сложността във времето и пространството на всеки от тези методи.
Както винаги, кодови фрагменти могат да бъдат намерени в GitHub.