Удаление дубликатов из строки в Java

Question

Я пытаюсь перебрать строку, чтобы удалить дублирующиеся символы.

Например, строка aabbccdef должна стать abcdef и строка abcdabcd должна стать abcd

Вот что у меня есть:

public class test {

    public static void main(String[] args) {

        String input = new String("abbc");
        String output = new String();

        for (int i = 0; i < input.length(); i++) {
            for (int j = 0; j < output.length(); j++) {
                if (input.charAt(i) != output.charAt(j)) {
                    output = output + input.charAt(i);
                }
            }
        }

        System.out.println(output);

    }

}

Каков наилучший способ сделать это?

Answer 1

Преобразуйте строку в массив char и сохраните ее в LinkedHashSet.Это сохранит ваш заказ и удалит дубликаты.Что-то вроде:

String string = "aabbccdefatafaz";

char[] chars = string.toCharArray();
Set<Character> charSet = new LinkedHashSet<Character>();
for (char c : chars) {
    charSet.add(c);
}

StringBuilder sb = new StringBuilder();
for (Character character : charSet) {
    sb.append(character);
}
System.out.println(sb.toString());

Answer 2

Попробуйте это простое решение:

public String removeDuplicates(String input){
    String result = "";
    for (int i = 0; i < input.length(); i++) {
        if(!result.contains(String.valueOf(input.charAt(i)))) {
            result += String.valueOf(input.charAt(i));
        }
    }
    return result;
}

Answer 3

Я бы воспользовался помощью LinkedHashSet . Удаляет дубликаты (так как мы используем Set, поддерживает порядок, как мы используем связанный список impl) Это своего рода грязное решение. может быть, даже лучший способ.

String s="aabbccdef";
Set<Character> set=new LinkedHashSet<Character>();
for(char c:s.toCharArray())
{
    set.add(Character.valueOf(c));
}

Answer 4

Использование Stream облегчает задачу.

import java.util.Arrays;
import java.util.stream.Collectors;

public class MyClass {

    public static String removeDuplicates(String myString) {
        return Arrays.asList(myString.split(""))
                     .stream()
                     .distinct()
                     .collect(Collectors.joining());
    }
}

Вот еще немного документации о Stream и все, что вы можете с ней сделать: https://docs.oracle.com/javase/8/docs/api/java/util/stream/package-summary.html

Часть 'описания' очень поучительна о преимуществах потоков.

Answer 5

Создать StringWriter.Запустите исходную строку, используя charAt (i) в цикле for.Поддерживайте переменную типа char, сохраняя последнее значение charAt.Если вы выполняете итерацию и значение charAt равно тому, что хранится в этой переменной, не добавляйте в StringWriter.Наконец, используйте метод StringWriter.toString (), получите строку и выполните с ней все, что вам нужно.

Answer 6

Я думаю, что работать таким образом было бы проще ,,, Просто передайте строку этой функции, и работа сделана :).

private static void removeduplicate(String name)
{   char[] arr = name.toCharArray();
    StringBuffer modified =new StringBuffer();
    for(char a:arr)
    {
        if(!modified.contains(Character.toString(a)))
        {
            modified=modified.append(Character.toString(a)) ;
        }
    }
    System.out.println(modified);
}

Answer 7

Код для удаления повторяющихся символов в строке без использования дополнительного буфера. ПРИМЕЧАНИЕ. Подойдут одна или две дополнительные переменные. Дополнительный массив не является:

import java.util.*;
public class Main{
    public static char[] removeDupes(char[] arr){
        if (arr == null || arr.length < 2)
            return arr;
        int len = arr.length;
        int tail = 1;
        for(int x = 1; x < len; x++){
            int y;
            for(y = 0; y < tail; y++){
                if (arr[x] == arr[y]) break;
            }
            if (y == tail){
                arr[tail] = arr[x];
                tail++;
            }
        }
        return Arrays.copyOfRange(arr, 0, tail);
    }

    public static char[] bigArr(int len){
        char[] arr = new char[len];
        Random r = new Random();
        String alphabet = "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ1234567890!@#$%^&*()-=_+[]{}|;:',.<>/?`~";

        for(int x = 0; x < len; x++){
            arr[x] = alphabet.charAt(r.nextInt(alphabet.length()));
        }

        return arr;
    }
    public static void main(String args[]){

        String result = new String(removeDupes(new char[]{'a', 'b', 'c', 'd', 'a'}));
        assert "abcd".equals(result) : "abcda should return abcd but it returns: " + result;

        result = new String(removeDupes(new char[]{'a', 'a', 'a', 'a'}));
        assert "a".equals(result) : "aaaa should return a but it returns: " + result;

        result = new String(removeDupes(new char[]{'a', 'b', 'c', 'a'}));
        assert "abc".equals(result) : "abca should return abc but it returns: " + result;

        result = new String(removeDupes(new char[]{'a', 'a', 'b', 'b'}));
        assert "ab".equals(result) : "aabb should return ab but it returns: " + result;

        result = new String(removeDupes(new char[]{'a'}));
        assert "a".equals(result) : "a should return a but it returns: " + result;

        result = new String(removeDupes(new char[]{'a', 'b', 'b', 'a'}));
        assert "ab".equals(result) : "abba should return ab but it returns: " + result;


        char[] arr = bigArr(5000000);
        long startTime = System.nanoTime();
        System.out.println("2: " + new String(removeDupes(arr)));
        long endTime = System.nanoTime();
        long duration = (endTime - startTime);
        System.out.println("Program took: " + duration + " nanoseconds");
        System.out.println("Program took: " + duration/1000000000 + " seconds");

    }
}

Как читать и говорить о вышеприведенном коде:

1. Метод с именем removeDupes принимает массив примитивных символов с именем arr.
2. arr возвращается как массив примитивных символов «по значению». Переданная arr - это сборка мусора в конце метода-члена Main removeDupes.
3. Сложность времени выполнения этого алгоритма составляет O (n) или, более конкретно, O (n + (малая константа)) константа, являющаяся уникальными символами во всем массиве примитивных символов.
4. copyOfRange значительно не увеличивает сложность среды выполнения, поскольку копирует только небольшое количество постоянных элементов. Массив char, называемый arr, не проходит весь путь.
5. Если вы передаете значение null в removeDupes, метод возвращает значение null.
6. Если вы передадите пустой массив примитивных символов или массив, содержащий одно значение, этот немодифицированный массив будет возвращен.
7. Метод removeDupes идет как можно быстрее физически, полностью используя кэш L1 и L2, поэтому Перенаправления веток поддерживаются на минимальном .
8. Неиспользованный компьютер стандартного выпуска 2015 года должен иметь возможность завершить этот метод с помощью массива примитивных символов, содержащего 500 миллионов символов, от 15 до 25 секунд.

Объясните, как работает этот код:

Первая часть переданного массива используется в качестве хранилища для уникальных символов, которые в конечном итоге возвращаются. В начале функции ответ: «символы от 0 до 1» от 0 до хвоста.

Мы определяем переменную y вне цикла, потому что мы хотим найти первое место, где индекс массива, на который мы смотрим, был продублирован в нашем хранилище. Когда дубликат найден, он вырывается и выходит, хвост y == возвращает false, а хранилище не добавляется.

когда индекс x, на который мы заглядываем, не представлен в нашем хранилище, тогда мы извлекаем его и добавляем в конец нашего хранилища в конце индекса и в хвосте приращения.

В конце мы возвращаем массив между точками 0 и хвостом, который должен быть меньше или равен по длине исходному массиву.

Упражнение «Говорящие точки» для интервью кодеров:

Будет ли программа вести себя иначе, если вы измените y ++ на ++ y? Почему или почему нет.

Представляет ли копия массива в конце еще один проход 'N' через весь массив, что делает сложность времени выполнения O (n * n) вместо O (n)? Почему или почему нет.

Можете ли вы заменить двойное равенство, сравнивая примитивные символы, на .equals? Почему или почему нет?

Можно ли изменить этот метод, чтобы сделать замены "по ссылке", а не как сейчас, "по значению"? Почему или почему нет?

Можете ли вы повысить эффективность этого алгоритма, отсортировав хранилище уникальных значений в начале 'arr'? При каких обстоятельствах это будет более эффективным?

Answer 8

Мне кажется, что все слишком стараются выполнить эту задачу.Все, что нас беспокоит, - это то, что он копирует 1 копию каждого письма, если оно повторяется.Тогда, потому что нас беспокоит только то, что эти символы повторяются один за другим, вложенные циклы становятся произвольными, так как вы можете просто сравнить позицию n с позицией n + 1. Тогда, потому что это копирует вещи только тогда, когда они разные, чтобы решитьПоследний символ вы можете либо добавить пробел в конец исходной строки, либо просто получить его, чтобы скопировать последний символ строки в ваш результат.

String removeDuplicate (String s) {

    String result = "";

    for (int i = 0; i < s.length(); i++){
        if (i + 1 < s.length() && s.charAt(i) != s.charAt(i+1)){
            result = result + s.charAt(i);
        }
        if (i + 1 == s.length()){
            result = result + s.charAt(i);
        }
    }

    return result;

}

Answer 9

Вот улучшение ответа Дэйва .

Он использует HashSet вместо немного более дорогостоящего LinkedHashSet и повторно использует буфер chars для результата, устраняя необходимость в StringBuilder.

String string = "aabbccdefatafaz";

char[] chars = string.toCharArray();
Set<Character> present = new HashSet<>();
int len = 0;
for (char c : chars)
    if (present.add(c))
        chars[len++] = c;

System.out.println(new String(chars, 0, len));   // abcdeftz

Answer 10

public class RemoveRepeated4rmString {

    public static void main(String[] args) {
        String s = "harikrishna";
        String s2 = "";
        for (int i = 0; i < s.length(); i++) {
            Boolean found = false;
            for (int j = 0; j < s2.length(); j++) {
                if (s.charAt(i) == s2.charAt(j)) {
                    found = true;
                    break; //don't need to iterate further
                }
            }
            if (found == false) {
                s2 = s2.concat(String.valueOf(s.charAt(i)));
            }
        }
        System.out.println(s2);
    }
}