[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
补充：综合编程 , 其他综合 ,
