[google面试CTCI]1-3.字符串去重

【字符串与数组】

Q：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
FOLLOW UP
Write the test cases for this method

题目：设计一个算法，在不使用额外存储空间的情况下，去掉字符串中重复的字符。（注：允许使用一个或者两个附件变量，但不能傻不拉几的把所有的字符复制一遍）

另外，写出你的测试用例。

解答：

方法一：暴力解法，时间复杂度为O(n3)。

从头至尾遍历字符串，对于每个字符，判断其后面的每个字符是否与其相同，如果相同，则将相同字符到字符串结尾的所有字符前移一位(相当于删除了该相同的字符)。

void remove_duplicate(char* str){if(str==NULL)return;int len=strlen(str);if(len<2)return;int i,j,k;for(i=0;i<len;++i)  for(j=i+1;j<len;++j)      if(str[i]==str[j]){  for(k=j+1;k<len;++k){str[k-1]=str[k];len--;  }       }str[len-1]='\0';}

方法二：优雅的解法,时间复杂度为O(n2)。

遍历字符串，遇到相同的字符，就将其置为’\0’。注意这里index变量的使用。

void remove_duplicate(char* str){if(str==NULL)return;int len=strlen(str);if(len<2)return;int i,j;int index=0;for(i=0;i<len;++i){if(str[i]!='\0'){str[index++]=str[i];for(j=i+1;j<len;++j){if(str[j]==str[i])str[j]='\0';}}}str[index]='\0';}

方法三：文艺一点的解法,时间复杂度为O(n)。

题目要求在不使用额外存储空间操作，我开辟一个常数大小的数组不为过吧？假设字符串都为ascii码不为过吧？如果可以开辟常数大小的空间，可以假设字符串都为ascii码字符，那么文艺范的思维是这样的：开辟两个256大小的数组，遇到一个字符，根据该字符的ascii码值，将数组对应的位置为1。所以，每次我们判断一个字符是不是重复出现的字符，只需要先看看数组中那个位置上是不是已经是1了，如果已经是1，那它之前出现过。

void remove_duplicate(char* str){if(str==NULL)return;int len=strlen(str);if(len<2)return;char flags[256];memset(flags,0,sizeof(flags));int i,j;int index=1;flags[str[0]]=1;for(i=1;i<len;++i){if(flags[str[i]]!=1){  str[index++]=str[i];  flags[str[i]]=1;}}str[index]='\0';}

测试用例：

1.不含重复字符的字符串，如abcdefg

2.全是重复字符的字符串，如aaaaaa

3.NULL字符串

4.空字符串

5.含有连续重复字符的字符串，如aaaabbbb

6.含有非连续重复字符的字符串，如ababab

作者：Viidiot 微信公众号：linux-code