431
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';
}
最後更新：2017-04-03 12:56:33