我的算法给我不正确的重复删除值有什么问题？

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

您可以使用distinct()：

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”，您的解决方案将很容易失败，因为当您尝试在索引 2 处找到“a”时，您将其删除并跳过与“实际”索引 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 开始），您将得到 string bannas。然后，当您要删除 的第三个 a 时bananas，在 pos 5，您最终会删除 s。