NO IMAGE

字元流中第一個不重複的字元 

時間限制:1秒 空間限制:32768K 

題目描述 

請實現一個函式用來找出字元流中第一個只出現一次的字元。例如,當從字元流中只讀出前兩個字元”go”時,第一個只出現一次的字元是”g”。當從該字元流中讀出前六個字元“google”時,第一個只出現一次的字元是”l”。

如果當前字元流沒有存在出現一次的字元,返回#字元。

題目分析

ASCII碼錶中一共包含128個字元,因此我們可以定義一個包含128個元素的陣列hashArray,同時定義一個存放第一個一共出現1次的字元的佇列data。

當插入一個字元ch時,hashArray[ch] 。如果ch為第一次出現,則插入隊尾。

當查詢第一個出現的字元時,如果佇列中第一個字元只出現一次,則返回第一個字元,否則彈出佇列,查詢下一個,直到佇列為空,或者找到第一個只出現一次的字元。程式碼實現如下:

程式碼實現 


class Solution
{
private:
unsigned char hashArray[128];
deque<char>data;
public:
//Insert one char from stringstream
void Insert(char ch)
{
hashArray[ch]  ;
if (hashArray[ch] == 1)
{
data.push_back(ch);
}
}
//return the first appearence once char in current stringstream
char FirstAppearingOnce()
{
while (data.size() != 0 && hashArray[data.front()] != 1)
{
data.pop_front();
}
if(data.size() == 0)
return '#';
return data.front();
}
};