删除字符串中的重复字符

Sam Lot 发表于 Dev

山姆·洛特（Sam Lot）

这来自破解《编码面试书》。

设计一种算法并编写代码以删除字符串中的重复字符，而无需使用任何其他缓冲区。注意：一个或两个其他变量都可以。不是数组的额外副本。

在书中它说时间复杂度是$ 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 
    }


 -

让·弗朗索瓦·萨瓦德

我完全依赖@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);
}