經典考題——無重複字元問題（查找字元串中第一個無重複字元）

題目描述：

尋求最佳的算法

 編寫一個高效率函數來找出一個字元串中第一個無重複字元.例如:”total”中的o,”teeter”中的r.要求算法效率優于O(n2)。

分析：個人覺得，這個題目如果不強調效率就有點簡單了吧，兩層循環弄一下應該沒問題了。但是另外一個角度，我覺得這個題目肯定是要周遊字元串的，是以算法效率最低應該就是O(n)吧，不知道是否是這樣。

在筆試群碩的時候，由于時間關系，這個題我沒有寫代碼，在隻有5分鐘的情況下，寫了個思路。我當時寫的是：

對字元串排序（用O(n)以下的方法，很多啦），然後周遊一次排序後的字元串。回來後，我發現我思路有問題，這樣做如何是找所有的無重複字元倒是可以，但是要找到第一個，就沒法了。

這個題目在網上看了一下，思路倒是不少，其中有個典型思路聽起來很簡單，很有效率，但是事實上太沒效率了。思路是：周遊字元串，如果目前字元在字元串中從前往後數和從後往前數的下标是一個數（在java和c++中有類的方法可以找到下标），那麼就說明無重複。一聽這思路，很簡潔啊，效率也不錯吧，其實不是，這裡調用的類的方法效率就很低了，這方法内部肯定要周遊字元串，效率沒有提高。

下面的代碼是我回來之後寫的，思路大概是：統計每個字元串的個數到字母表數組中，并且統計對應的出現的下标到索引數組，然後再周遊字母表數組，根據個數判斷是否是重複的，并到索引數組中查找對應的下标是不是最小的（最前面的），就可以得到是哪一個字元是第一個無重複的了。

/*

編寫一個高效率函數來找出一個字元串中第一個無重複字元.例如:”total”中的o,”teeter”中的r.

要求算法效率優于O(n2).

*/

#include <iostream>

using namespace std;

char findStr(const char* str)

{

int len=strlen(str),count[26],index[26];

char result,curr;

for(int j=0;j<26;j++)

{

count[j]=0;

index[j]=0;

}

bool exist=false;

for(int i=len;i>0;i--)

{

curr=str[i-1];

count[curr-'a']++;

index[curr-'a']=i-1;

}

int minIndex=len+1;

for(i=0;i<26;i++)

{

if(count[i]==1)

{

if(index[i]<minIndex)

{

minIndex=index[i];

}

}

}

return str[minIndex];

}

int main()

{

const char* test="aac";

cout<<findStr(test)<<endl;

return 0;

}

以下代碼和上面代碼思路類似，但是更巧妙一點，沒有記錄索引，效率也為O(n)：

參考如下網頁：http://www.360doc.com/content/06/1023/12/11192_237819.shtml

/*

編寫一個高效率函數來找出一個字元串中第一個無重複字元.例如:”total”中的o,”teeter”中的r.

要求算法效率優于O(n2).

*/

#include <iostream>

using namespace std;

char findStr(const char* str)

{

int p[256];

int i,j;

for(i=0;i<256;i++)

p[i]=0;

i=0;

while(str[i]!='/0')

{

p[str[i]]++;

i++;

}

for(i=0;str[i]!='/0';i++)

{

if(p[str[i]]==1)

{

return str[i];

}

}

return 0;

}

int main()

{

const char* test="acacdcefe";

cout<<findStr(test)<<endl;

return 0;

}

網上還有一些其他解法吧，甚至用到了哈希的，不管了，以上兩個程式已經很不錯了。