[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

补充：综合编程 , 其他综合 ,