在一个字符串中去除重复的字符

Question

这是来自《Cracking the Coding Interview》书中的内容。

设计一个算法并编写代码，以在不使用任何额外缓冲区的情况下删除字符串中的重复字符。注意：使用一个或两个额外变量是可以的，但不能使用数组的额外副本。

根据书中所说，时间复杂度为$O(N^2)$。我们如何从解决方案中确定时间复杂度为$O(N^2)$？我对解决方案如何去除重复字符有疑问，我已经在下面的内联注释中包含了它们。

   public static void removeDuplicates(char[] str) {
      if (str == null) return; // if the array is empty return  nothing?
      int len = str.length; // get the length of the array 
      if (len < 2) return; // if the array length is only 1 return nothing?
      int tail = 1; // initialise tail variable as 1 ! 
      // Why are we starting at second character here (at i = 1),why not start at i = 0 ? 
      for (int i = 1; i < len; ++i) { 
        int j;

        for (j = 0; j < tail; ++j) { // so are we checking if j is less then 1 as tail has been initialized to 1 
          if (str[i] == str[j]) break; // stop, if we find duplicate.
        }

        if (j == tail) { why are we comparing j to tail(1) here ?
          str[tail] = str[i]; // assigning the value 
          ++tail; // incrementing tail
        }
      }
      str[tail] = 0; //setting last element as 0 
    }


 - 

- Sam Lot

---

你说这个方法在一本书里？它不起作用。我尝试过 char[] arr = {'a','b','a','b'};removeDuplicates(arr);System.out.println(Arrays.toString(arr));，输出是 [a, b, , b]。 - Paul Boddington

字符串中字符出现的顺序是否重要？如果不重要，则可以对给定数组应用“快速排序”以对数组的每个元素进行排序，这将具有O（n log n）的复杂度。然后简单地遍历数组（复杂度为O（n）），并仅存储您第一次遇到的那些字符，因为每个元素都是按递增顺序排列的，例如a、b、b、c、c、c、d，从index = 1开始，检查该值是否等于compareWith = index - 1处的值。如果它们不相等，则将其附加到某个变量中，这样您就会得到唯一的出现次数。 - nIcE cOw

代码是正确的，但这只是伪代码，没有人说它是Java。在Java中，0不会终止字符串。在C中，0或'\0'会终止字符串。 @pbabcdefp您的输出是正确的答案，如果您在空字符处停止读取字符串。 - Adam Ocsvari

@AdamOcsvari 哦，我明白了，所以楼主试图将一些伪代码翻译成Java，但是做错了。没关系。 - Paul Boddington

请注意，他的问题与逻辑无关。大O表示法并不真正关心它是否完成了特定的任务。 - gobbly

Answer 1

我完全依赖@pbabcdefp的评论，因为我太懒了，无法测试它，但似乎您的算法不起作用。

无论如何，我不喜欢它，下面是我如何做以及注释解释：

public static void main(String[] args) {
    removeDuplicates(new char[]{'a','a','b','b','c','d','c'});
}

public static final void removeDuplicates(char[] str)
{
    /*
     * If the str is not instantiated, or there is maximum 1 char there is no need to remove duplicates as 
     * it is just impossible to have duplicate with 1 char.
    */
    if (str == null || str.length < 2)
        return;

    //loop over each char
    for(int i = 0; i < str.length; i++)
    {
        //no need to check with earlier character as they were already checked, so we start at i + 1
        for(int j = i + 1; j < str.length; j++)
        {
            //if they match we clear
             if(str[j] == str[i])
                str[j] = ' ';
        }
    }

    System.out.println(str);
}

这会输出a b cd。

- Jean-François Savard

---

这是一个错误的解决方案！你可以争论任务定义不清，但如果我想要从一个字符串中去除重复的部分，这并不意味着用其他字符来替换字符串中的重复部分。 如果你需要移除，那么字符串就变得更短了。如果我的字符串有1000个'a'字符，那么最终我只希望得到一个只有1个字符长度的字符串。 - Adam Ocsvari

@AdamOcsvari 我知道，我只是提供了识别重复字符的算法。这通常是我的回答方式，我不喜欢过度解释。我相信从这里起，原帖作者应该能够理解自己所问的问题。 - Jean-François Savard

重写他的逻辑如何回答他的问题？这不是在“喂食”吗？ - gobbly

Answer 2

首先，这是一本非常好的书，我希望向大家推荐！

通常情况下，如果您被允许使用大量内存，那么您可以节省时间；如果只允许使用少量变量，则仍然可以通过更慢的算法解决此问题。此外，还有完整的暴力算法，即检查每个可能的解决方案。

public static void removeDuplicates(char[] str) {
  if (str == null) return; // if the array is empty return  nothing?

输入是一个字符串指针，因此该字符串存在于内存中的某个位置，代码可能会修改它，但它仍然在原来的位置。这就是函数返回类型为void的原因，因为它不返回任何东西。当函数返回时，原始位置上的字符串没有重复。

  int len = str.length; // get the length of the array 
  if (len < 2) return; // if the array length is only 1 return nothing?

与上面相同，没有返回值。如果字符串少于2个字符，则不能包含重复项。

从这里开始逻辑如下： 取第i个字符。检查它在字符串中是否存在。如果存在，则算法删除第i个字符。如果不存在，则保留在字符串中。

证明这是正确的算法： 字符串中不存在任何早期存在的字符。如果一个字符后来存在于字符串中，它将因为前面的规则而被删除。

如果这是算法，它将工作得很好，但是字符串中会有“空”字符。字符串不会变小，尽管它应该包含更少的字符。

这就是为什么算法跟踪“输出字符串的尾部”。这就是为什么尾巴在开始时等于1，因为第一个字符肯定是结果字符串的一部分。 当当前字符应该被删除时，输出字符串的尾部不会移动，结果不会添加新字符。当当前字符应该是结果的一部分时，它会被复制到结果字符串的尾部。

当算法到达输入字符串的末尾时，它关闭了结果字符串。

复杂度： 这意味着相对于输入大小（称为'n'）,算法需要执行多少步骤。通常只计算循环和递归次数。 此代码嵌套了两个for循环。 外部循环每次从1到n。 内部循环从0到tail，其中tail从1到n。因此，在最坏的情况下，内部循环平均从1到n/2。 这意味着您的复杂度为n *（n / 2）。由于2是一个常数，所以您的复杂度是n * n。

- Adam Ocsvari

---

之前字符串中的任何字符都不会保留。你试过吗？ - Paul Boddington

不，我没有尝试运行伪代码。但我可以看出，为什么你在Java上得到了错误的答案。https://dev59.com/kmMl5IYBdhLWcg3wa2fW - Adam Ocsvari

Answer 3

O时间复杂度是关于最坏情况的。忽略你得到的数组和你对它执行的操作，当你有两个嵌套的for循环受到字符串长度的限制时，你的复杂度不能高于n^2，因此它是O(n^2)（这只是一个上界，如果你想显示它也是一个下界，需要做更多的工作）。

- Matan Liram

---

一般而言，您是正确的，但让我们就此达成共识：2次循环并不意味着最大复杂度为O(n^2)。您可能会在循环内部使用递归或者对循环变量进行棘手的修改。甚至仅有一次循环，也可能导致无限循环。 - Adam Ocsvari

递归会改变游戏规则，但是没有它，我相信字符串长度限制已经足够了。 - Matan Liram

Answer 4

O(N^2)基本上意味着随着输入数量的增加，N代表输入数量，复杂度（执行操作的次数）将与N^2成比例增加，再加上一些常量值。

看看代码，str.length就是N。对于每个元素，您将其与其他每个元素进行比较，N次比较N次=N^2。

现在，O(N^2)并不意味着准确。根据定义，它只关注对复杂度增长有贡献的非常数因素。它永远不会告诉您特定算法运行的速度有多快，它纯粹只告诉您随着被操作元素数量的波动，运行所需时间将如何扩展。

- gobbly

Answer 5

使用此代码以删除所有重复的小写字母

static boolean contains(char c, char[] array) {
    for (char x : array) {
        if (x == c) {
            return true;
        }
    }
    return false;
}
public static void main(String[] args) {
String s = "stackoverflow11221113" ;

String result = "";
for(char ch:s.toCharArray()){
  if(!contains(ch,result.toCharArray())){
    result +=ch;
  }
}
System.out.println(result);
}

使用此方法删除所有重复的字符，无论是小写还是大写

static boolean contains(char c, char[] array) {
    for (char x : array) {
        if (x == c) {
            return true;
        }
    }
    return false;
}
public static void main(String[] args) {
String s = "StackOverFlow11221113" ;
String result = "";
for(char ch:s.toCharArray()){
  if(!contains(ch,result.toLowerCase().toCharArray())){
    result +=ch;
  }
}
System.out.println(result);
}

- Mengtong Un