转载请注明出处: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