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

NO IMAGE

題目描述:
實現一個函式用來找出字元流中第一個只出現一次的字元。
分析:
使用ASCII字符集只有256個字元,可以定義一個長度為256的陣列,使得陣列下標對應的的記錄字元出現的位置,初始時陣列的每個元素都初始化為-1. 每遇到一個字元,先判斷在陣列中的對應位置上的值是否為-1,若是,則表示當前遇到的字元是第一次出現,就將對應位置改為1;若陣列的對應位置不是-1,則表示當前遇到的字元已經出現過了,則把陣列當前位置的值變為-2. 持續次過程直到讀完所有字元,然後遍歷陣列,找到陣列中存在的不是-2的最小數,並該元素對應的下標轉換成字元就可得到第一個只出現一次的字元.

class func{
private:
int arr[256];
int index;
public:
func(): index(0) {
for(int i  = 0; i < 256; i  )
arr[i] = -1;
}
void InsertChar(char ch){
if(arr[(int)ch] == -1){
arr[(int)ch] = index; 
}else{
arr[(int)ch] = -2;
}
Index  ;
}
char FirstAppearingOnce(){
char ch = '#';
int MIN = (int)((unsigned)~0 >> 1);
for(int i = 0; i < 256; i  ){
if(arr[i] >= 0 && arr[i] < MIN){
ch = (int) i;
MIN = arr[i];           
}
}
return ch;
}   
};