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

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

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

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

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

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

　　我們第一遍掃描這個(gè)數(shù)組時(shí)，每碰到一個(gè)字符，在哈希表中找到對(duì)應(yīng)的項(xiàng)并把出現(xiàn)的次數(shù)增加一次。這樣在進(jìn)行第二次掃描時(shí)，就能直接從哈希表中得到每個(gè)字符出現(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)推薦：

　　2017年計(jì)算機(jī)軟件水平考試時(shí)間公布(全年)

　　各地2017年軟件水平考試準(zhǔn)考證打印/領(lǐng)取時(shí)間匯總

　　考試吧特別策劃：2017年計(jì)算機(jī)軟考報(bào)考指南專題

　　軟考各科目模擬試題及答案※各科目復(fù)習(xí)指導(dǎo)匯總

　　軟考報(bào)考條件※軟考報(bào)名方法※考試大綱※科目

　　歷年軟考真題及答案匯總※軟件水平考試簡(jiǎn)介