軟件水平

-第一個只出現(xiàn)一次的字符

題目：在一個字符串中找到第一個只出現(xiàn)一次的字符。如輸入abaccdeff，則輸出b。

分析：這道題是2006年google的一道筆試題。

看到這道題時，最直觀的想法是從頭開始掃描這個字符串中的每個字符。當訪問到某字符時拿這個字符和后面的每個字符相比較，如果在后面沒有發(fā)現(xiàn)重復(fù)的字符，則該字符就是只出現(xiàn)一次的字符。如果字符串有n個字符，每個字符可能與后面的O(n)個字符相比較，因此這種思路時間復(fù)雜度是O(n2)。我們試著去找一個更快的方法。

由于題目與字符出現(xiàn)的次數(shù)相關(guān)，我們是不是可以統(tǒng)計每個字符在該字符串中出現(xiàn)的次數(shù)?要達到這個目的，我們需要一個數(shù)據(jù)容器來存放每個字符的出現(xiàn)次數(shù)。在這個數(shù)據(jù)容器中可以根據(jù)字符來查找它出現(xiàn)的次數(shù)，也就是說這個容器的作用是把一個字符映射成一個數(shù)字。在常用的數(shù)據(jù)容器中，哈希表正是這個用途。

哈希表是一種比較復(fù)雜的數(shù)據(jù)結(jié)構(gòu)。由于比較復(fù)雜，STL中沒有實現(xiàn)哈希表，因此需要我們自己實現(xiàn)一個。但由于本題的特殊性，我們只需要一個非常簡單的哈希表就能滿足要求。由于字符(char)是一個長度為8的數(shù)據(jù)類型，因此總共有可能256 種可能。于是我們創(chuàng)建一個長度為256的數(shù)組，每個字母根據(jù)其ASCII碼值作為數(shù)組的下標對應(yīng)數(shù)組的對應(yīng)項，而數(shù)組中存儲的是每個字符對應(yīng)的次數(shù)。這樣我們就創(chuàng)建了一個大小為256，以字符ASCII碼為鍵值的哈希表。

我們第一遍掃描這個數(shù)組時，每碰到一個字符，在哈希表中找到對應(yīng)的項并把出現(xiàn)的次數(shù)增加一次。這樣在進行第二次掃描時，就能直接從哈希表中得到每個字符出現(xiàn)的次數(shù)了。

參考代碼如下：

///////////////////////////////////////////////////////////////////////

// Find the first char which appears only once in a string

// Input: pString - the string

// Output: the first not repeating char if the string has, otherwise 0

///////////////////////////////////////////////////////////////////////

char FirstNotRepeatingChar(char* pString)

{

// invalid input

if(!pString)

return 0;

// get a hash table, and initialize it

constinttableSize =256;

unsignedinthashTable[tableSize];

for(unsignedinti = 0; ihashTable[i] = 0;

// get the how many times each char appears in the string

char* pHashKey = pString;

while(*(pHashKey) != '\0')

hashTable[*(pHashKey++)] ++;

// find the first char which appears only once in a string

pHashKey = pString;

while(*pHashKey != '\0')

{

if(hashTable[*pHashKey] == 1)

return *pHashKey;

pHashKey++;

}

// if the string is empty

// or every char in the string appears at least twice

return 0;

}

相關(guān)推薦：

計算機軟件水平考試輔導(dǎo)資料

計算機軟件水平考試精品輔導(dǎo)班

（責任編輯：）

共2頁,當前第1頁  第一頁  前一頁  下一頁