今天博彥面試的一道題

面試官問到：給定一個字元串，請處理成一個沒有重複字元的字元串

當時想到的是一個簡單但性能普通的方法，這個方法普通人都能想得到

吃完飯後我回到寝室，分析不能每次判斷有沒有重複都去周遊已周遊過的每個字元

為此，想到了數組的直接存取性質，于是豁然開朗：

算法差不多是這樣的：

假設char str[]="bavdfegsgah$ #@";

那麼先建立一個字典映射函數//其實相當于建立了索引

int indexStr(char c)

{

if(c=='a') return 0;

else if(c=='b') return 1;

...

else return -1;

}

//main

int[] s1=new int[indexStrCount];//indexStrCount為字典中字元的個數

int[] s2=new int[indexStrCount];

int i,j;

for (i=0;i<strLength;i++)//strLength為str中字元的個數

s1[i]=0;

for (i=0,j=0;i<strLength;i++)

    if(s1[indexStr(str[i])]==0)//判斷該字元是否重複(存在時s1[i]=1)過

   {

   s1[i]=1;

   s2[j++]=str[i];

   if(j>=indexStrCount)break；

   }

//最後s2就是不重複的字元串，當然還可以考慮得更全面，上面的算法時間複雜度是T(n);

//一般人的第一次想法是判斷目前字元有沒有在已周遊的數組裡面(此時要周遊該數組)，這樣時間複雜度就增大為T(n^2);

昨晚睡覺前又想了下，indexStr（）函數似乎也類似周遊，看來得使用ASCII表和漢字編碼表，将字元和整數進行映射，比如字元'a'對應65，這樣可以直接從字元找到數組下标，就可以用到數組的直接存取功能了