转载请注明出处：http://blog.csdn.net/ns_code/article/details/21328151
题目：
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.
翻译：
移除字符串中重复的字符，如abcadc移除后变为abcd，可以额外定义一两个变量，但不允许额外开辟一个数组。并为该算法写测试用例。
思路：
本题目主要是限制了空间复杂度，如果没有这个要求，我们可以有很优的解法（假设字符串中的字母都是小写字母）：
比如当字符串很长时，我们可以采取同Q1.1题目中相同的思路，开设一个大小为26的bool数组，初始值为false，遍历字符串，第一次遇到某个字符，将该字符在bool数组中对应位置的元素置为true，如果再次遇到，说明出现了重复字符，将该字符移除即可。
再比如，如果字符串不是很长，那我们可以考虑采用KMP算法中的前缀数组，开辟一个比字符串长度大1的数组（对最后一个字符‘\0‘同样要求其前缀值）来作为该字符串的前缀数组，如果前缀数组中的值next[i]>0，则说明该位置前面连续next[i]个位置上的字符与前面的字符重复，可以将这些字符移除。
但是这里要求了空间复杂度为O（1），那我们只能用最简单的遍历方法，先让第一个字符与后面的字符一一比较，遇到重复的就把重复的字符用‘\0‘替换掉，再让第二个字符与右面的字符一一比较，遇到重复的，就把重复的字符用‘\0‘代替，如此循环，直到最后一个字符，当然同时还要在每次遇到‘\0‘时（重复字符出现的位置，已被填充为‘\0‘），将后面的字符移到前面来，替换掉‘\0‘，最后将移位后的最后一个位置设为‘\0‘，标志该字符串的结束。时间复杂度为O（n*n）。
测试用例我们需要考虑如下几种情况：
char str1[] = "abcdfbdk"; //随机字符串
char str2[] = "abababab"; //重复字符交替出现
char str3[] = "aaaabbbb"; //重复字符连续出现
char str4[] = "aaaaaaaa"; //全是重复字符
char str5[] = "abcdefgh"; //没有重复字符
char str6[] = ""; //空字符串
实现代码：
/***********************************************
题目描述：
移除字符串中重复的字符，如abcadc移除后变为abcd，
可以额外定义一两个变量，但不允许额外开辟一个数组,
并为该算法写测试用例
Date:2014-03-16
************************************************/
#include<stdio.h>
#include<string.h>
void remove(char *str)
{
int len = strlen(str);
if(len<2)
return;
int i,j;
int p = 0; //p的初值与i相等，均为0
for(i=0;i<len;i++)
{
//如果该字符不为‘\0‘，则与下面的字符比较
if(str[i])
{
//如果当前字符不为‘\0‘时，p一直与i相等，
//如果当前字符为‘\0‘，则p会小于i，从而用后面的字符来填充前面‘\0‘字符的位置
str[p++] = str[i];
//每个字符与其后面的字符比较，
//如果出现重复字符，则将后面的重复字符用‘\0‘代替
for(j=i+1;j<len;j++)
if(str[i] == str[j])
str[j] = ‘\0‘;
}
}
str[p] = ‘\0‘;
}
int main()
{
char str1[] = "abcdfbdk"; //随机字符串
char str2[] = "abababab"; //重复字符交替出现
char str3[] = "aaaabbbb"; //重复字符连续出现
char str4[] = "aaaaaaaa"; //全是重复字符
char str5[] = "abcdefgh"; //没有重复字符
char str6[] = ""; //空字符串
remove(str1);
remove(str2);
remove(str3);
remove(str4);
remove(str5);
remove(str6);
puts(str1);
puts(str2);
puts(str3);
puts(str4);
puts(str5);
puts(str6);
return 0;
}下面再给出一个开辟固定大小的bool数组的方法，也就是我们分析中的第一种方法，实现代码如下：
/*
开辟长为26的bool数组的方法
*/
void remove1(char *str)
{
int len = strlen(str);
if(len < 2)
return ;
int i;
int p = 0;
bool A[MAX];
memset(A,0,sizeof(A));
for(i=0;i<len;i++)
{
int index = str[i] - ‘a‘;
if(!A[index])
{
str[p++] = str[i];
A[index] = true;
}
}
str[p] = ‘\0‘;
}测试结果：
原文：http://blog.csdn.net/liuxuejiang158blog/article/details/21417145