去除字符串中重復字符

題目

設計算法并寫出代碼移除字符串中重復的字符，不能使用額外的緩存空間。注意： 可以使用額外的一個或兩個變量，但不允許額外再開一個數組拷貝。

進一步地，

為你的程序寫測試用例。

解答

這道題目其實是要你就地(in place)將字符串中重復字符移除。你可以向面試官問清楚， 不能使用額外的一份數組拷貝是指根本就不允許開一個數組，還是說可以開一個固定大小， 與問題規模(即字符串長度)無關的數組。

如果根本就不允許你再開一個數組，只能用額外的一到兩個變量。那么，你可以依次訪問 這個數組的每個元素時間復雜度為O(n2?)，代碼如下：

#include<iostream>
#include<cstring>
using namespace std;void removeDuplicate(char *str)
{if(str==NULL)return;int count=0;int n=strlen(str);for(int i=1;i<n;++i){int j=i-1;while(j>=0){if(str[i]==str[j]){++count;break;}else--j;}if(j<0)str[i-count]=str[i];}str[n-count]='\0';
}int main()
{char str[]="";removeDuplicate(str);cout<<str<<endl;
}

如果可以開一個固定大小，與問題規模(即字符串長度)無關的數組，那么可以用一個數組來 表征每個字符的出現(假設是ASCII字符，則數組大小為256)，這樣的話只需要遍歷一遍字符 串即可，時間復雜度O(n)。代碼如下：

void removeDuplicate(char s[])
{int len = strlen(s);if(len < 2) return;bool c[256];memset(c, 0, sizeof(c));int p = 0;for(int i=0; i < len; ++i){if(!c[s[i]]){s[p++] = s[i];c[s[i]] = true;}}s[p] = '';    
}

?