首页 > 代码库 > CareerCup之1.3字符串去重
CareerCup之1.3字符串去重
【题目】
原文:
1.3 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.
译文:
设计算法并写出代码移除字符串中反复的字符,不能使用额外的缓存空间。注意: 能够使用额外的一个或两个变量,但不同意额外再开一个数组拷贝。
【分析】
这道题目事实上是要你就地(in place)将字符串中反复字符移除。你能够向面试官问清楚, 不能使用额外的一份数组拷贝是指根本就不同意开一个数组,还是说能够开一个固定大小, 与问题规模(即字符串长度)无关的数组。
依据面试官的回答,制定对应的解题策略。
【思路一】
假设根本就不同意你再开一个数组,仅仅能用额外的一到两个变量。那么,最先想到的方法就是暴力求解法了。
你能够依次訪问这个数组的每一个元素,每訪问一个,就将该元素与前面的元素进行比較,假设同样就去掉,假设不同样就加入到前面序列中。
时间复杂度为O(n^2)
对应代码为代码一
【思路二】
假设根本就不同意你再开一个数组,仅仅能用额外的一到两个变量。另外一种方法就是先排序,再去重。
排序之后反复元素必然是相邻的,这样去重就简单多了。
排序时间复杂度最快为高速排序为O(nlogn)
去重时间复杂度为O(n)
终于为O(nlogn)
对应代码为代码二
【思路三】
1 如果能够开一个固定大小,与问题规模(即字符串长度)无关的数组,那么能够用一个数组来 表征每一个字符的出现(如果是ASCII字符,则数组大小为256),这种话仅仅须要遍历一遍字符 串就可以,时间复杂度O(n)。
对应代码为代码三
2 假设字符集更小一些,比方仅仅是a-z,即字符串里仅仅包括小写字母,那么使用一个int变量中 的每一位来表征每一个字符的出现,用位运算来实现。也能够在O(n)的时间里移除反复字符,并且还不须要额 外开一个数组。
对应代码为代码四
【代码一】
/********************************* * 日期:2014-5-6 * 作者:SJF0115 * 题目: 字符串中字符去重 * 来源:CareerCup **********************************/ #include <iostream> #include <algorithm> #include <string.h> using namespace std; //删除一个字符串中反复字符 void RemoveDuplicates(char str[]){ int i,j; if(str == NULL){ return; } int len = strlen(str); //去重 int index = 0; for(i = 0;i < len;i++){ //str[i]为待考察的元素 与前面元素比較看是否反复 for(j = 0;j < i;j++){ //有反复的元素 if(str[i] == str[j]){ break; } } //str[i] 前面没有与之反复的元素 if(j >= i){ str[index++] = str[i]; } } str[index] = ‘\0‘; } int main() { char str[] = "abababa"; RemoveDuplicates(str); cout<<str<<endl; return 0; }
【代码二】
//删除一个字符串中反复字符 void RemoveDuplicates(char str[]){ if(str == NULL){ return; } int len = strlen(str); //排序 sort(str,str+len); int index = 1; //去重 for(int i = 1;i < len;i++){ if(str[i] != str[i-1]){ str[index++] = str[i]; } } str[index] = ‘\0‘; }
【代码三】
//删除一个字符串中反复字符 void RemoveDuplicates(char str[]){ bool vis[256]; //初始化 memset(vis,false,sizeof(vis)); int len = strlen(str); int index = 0; for(int i = 0;i < len;i++){ if(!vis[str[i]]){ str[index++] = str[i]; vis[str[i]] = true; } } str[index] = ‘\0‘; }
【代码四】
void RemoveDuplicates(char str[]){ int len = strlen(str); if(len < 2) return; int check = 0; int index = 0; //去重 for(int i=0; i<len; ++i){ int v = (int)(str[i]-‘a‘); if((check & (1<<v))==0){ str[index++] = str[i]; check |= (1<<v); } } str[index] = ‘\0‘; }