Что не так с моим алгоритмом, который дает мне неправильные значения удаления дубликатов?

Question

Я пытаюсь удалить дубликаты в строке, но я не уверен, почему мой алгоритм неверен.Это дает мне вывод baa вместо bans, что является правильным выводом.

Во время попытки отладки я попытался переключить i на j внутри sb.deleteCharAt();, но это дало мне ошибку Exception in thread "main" java.lang.StringIndexOutOfBoundsException: String index out of range: 5.

Что я делаю неправильно и какя могу это исправить?

Вот мой код:

public static void removeDuplicate(String s) {
    StringBuilder sb = new StringBuilder(s);

    for(int i = 0; i < s.length(); i++) {
        for(int j = i + 1; j < s.length(); j++) {
            if(s.charAt(i) == s.charAt(j)) {
                sb.deleteCharAt(i);
            }
        }
    }
    System.out.print("Duplicates have been, the resulting string is => " + sb);
}

public static void main(String[] args) {
    String s = "bananas";
    removeDuplicate(s);
}

Answer 1

Вы можете использовать Different () :

StringBuilder sb = new StringBuilder();
yourstr.chars().distinct().forEach(c -> sb.append((char) c));

Лучший

Answer 2

Есть пара вещей, которые не правы. Вы должны делать сравнение со строителем строк в своих циклах, а не с самой строкой, поскольку она изменяется. Во-вторых, вы используете неверный индекс при удалении. Вот правильная программа:

public static void removeDuplicate(String s) {
    StringBuilder sb = new StringBuilder(s);

    for(int i = 0; i < sb.length(); i++) {
        for(int j = i + 1; j < sb.length(); j++) {
            if(sb.charAt(i) == sb.charAt(j)) {
                sb.deleteCharAt(j);
            }
        }
    }
    System.out.print("Duplicates have been, the resulting string is => " + sb);
}

public static void main(String[] args) {
    String s = "bananas";
    removeDuplicate(s);
}

Вывод:

Дубликаты были, результирующая строка => bans

Answer 3

Что ж, удаление элементов из коллекции во время цикла по ней - плохая идея, потому что это может привести к неправильной логике при изменении индекса. Просто поместите какой-то особый случай, например, «baaana», ваше решение легко потерпит неудачу, потому что когда вы пытаетесь найти «a» в индексе 2, вы удаляете его и пропускаете сравнение с «фактическим» индексом 3, потому что его индекс уменьшается до 2 после удаления , И еще одна вещь, которую вы должны знать. В Java String является неизменным, это означает, что когда вы изменяете строку, вы фактически присваиваете переменную с новой. Таким образом, эти функции должны возвращать новую строку вместо изменения ввода.

С этим типом проблемы, я предлагаю вам использовать хеш-тип данных для запоминания отдельных элементов, чтобы вы могли решить это с O (n) сложностью по времени.

public static String removeDuplicate(String s) {
    StringBuilder sb = new StringBuilder();
    Set<Character> metChars = new HashSet<>();
    for(int i = 0; i < s.length(); i++) {
        char c = s.charAt(i);
        if(!metChars.contains(c)) {
            sb.append(c);
            metChars.add(c);
        }
    }
    return sb.toString();
}

Answer 4

Как правило, когда вы удаляете символ из вашего StringBuilder, вы фактически изменяете индексы всех последующих символов.

В вашем примере bananas, если вы удалите второй a (поз. 3, так как мы начинаем с 0), вы получите строку bannas. Затем, когда вы хотите удалить 3-е a из bananas, в поз. 5 вы в конечном итоге удалите s.