在一个字符串中删除重复的字符 [英] Remove the duplicate characters in a string

问题描述

这是从破解编码面试书。

  

设计一个算法，写code删除字符串中的重复的字符
  而无需使用任何额外的缓冲液。注：一个或两个额外的变量都是精品。
  数组的额外副本是没有的。

在书中说，它的时间复杂度为$ O（N ^ 2）$。我们怎么可以告诉大家，时间复杂度为$ O（N ^ 2）$从解决？
我有一个问题，即解决如何删除重复的字符。我在下面的行内注释包含它们。

 公共静态无效removeDuplicates（的char [] STR）{
      如果（STR == NULL）回报; //如果数组是空的任何回报？
      INT LEN = str.length; //获取阵列的长度
      如果（LEN 2）回报; //如果数组长度只有1任何回报？
      INT尾= 1; //初始化尾巴变量1！
      //为什么我们开始第二个字符位置（在I = 1），为什么不在我= 0开始？
      的for（int i = 1; I＆LT; LEN ++我）{
        诠释J;        为（J = 0; J＆LT;尾巴; ++ j）条{//等都是我们检查，如果j是小于1的尾部已经被初始化到1
          如果（STR [I] ==海峡[J]）破; //停止，如果发现重复的。
        }        如果（J ==尾）{为什么我们比较J即可尾（1）在这里？
          海峡[尾] = STR [I] //分配值
          ++尾; //递增尾
        }
      }
      海峡[尾] = 0; //最后一个元素设置为0
    }
  - 
 

解决方案

我完全地依靠@pbabcdefp评论因为我懒，以测试它，但它看起来像你的算法是行不通的。

我不喜欢它无论如何，我会在这里如何与注释解释做到这一点：

 公共静态无效的主要（字串[] args）{
    removeDuplicates（新的char [] {'A'，'A'，'B'，'B'，'C'，'D'，'C'}）;
}公共静态最终无效removeDuplicates（的char [] STR）
{
    / *
     *如果STR不是实例，或者有最大1字符，没有必要删除重复的
     *它只是不可能有重复的1字符。
    * /
    如果（STR ==空|| str.length 2）
        返回;    //循环每个字符
    的for（int i = 0; I＆LT; str.length;我++）
    {
        //不需要检查与早期的字符作为他们已经检查，所以我们开始在I + 1
        对于（INT J = I + 1; J＆LT; str.length; J ++）
        {
            //如果匹配，我们清除
             如果（STR [J] ==海峡[I]）
                海峡[J] ='';
        }
    }    的System.out.println（STR）;
}
 

这将输出 A B CD 。

This is from cracking the Coding Interview Book.

Design an algorithm and write code to remove the duplicate characters in a string without using any additional buffer. NOTE: One or two additional variables are fine. An extra copy of the array is not.

In the book it says time complexity is $O(N^2)$. How can we tell that the time complexity is $O(N^2)$ from the solution? I have questions as to how the solution is removing duplicate characters. I have included them in the inline comments below.

   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 
    }


 - 

解决方案

I completly rely on @pbabcdefp comment as I'm to lazy to test it, but it seems like your algorithm does not work.

I did not like it anyway, here how I would do it with explanation in comments :

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);
}

That would output a b cd.

这篇关于在一个字符串中删除重复的字符的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！