[劍指offer] 字元流中第一個不重複的字元

本文首發于我的個人部落格： 尾尾部落

題目描述

請實作一個函數用來找出字元流中第一個隻出現一次的字元。例如，當從字元流中隻讀出前兩個字元"go"時，第一個隻出現一次的字元是"g"。當從該字元流中讀出前六個字元“google"時，第一個隻出現一次的字元是"l"。

解題思路

用一個哈希表來存儲每個字元及其出現的次數，另外用一個字元串 s 來儲存字元流中字元的順序。

• 每次插入的時候，在字元串 s 中插入該字元，然後在哈希表中檢視是否存在該字元，如果存在則它的 value 加1，如果不存在，它在哈希表中插入該字元，它的 value 為 1。
• 查找第一個隻出現一次的字元時，按照 s 的順序，依次查找 map 中字元出現的次數，當 value 為 1 時，該字元就是第一個隻出現一次的字元。

參考代碼

import java.util.HashMap;
public class Solution {
    HashMap<Character, Integer> map = new HashMap<Character, Integer>();
    StringBuffer s = new StringBuffer();
    //Insert one char from stringstream
    public void Insert(char ch)
    {
        s.append(ch);
        if(map.containsKey(ch)){
            map.put(ch, map.get(ch)+1);
        }else{
            map.put(ch, 1);
        }
    }
  //return the first appearence once char in current stringstream
    public char FirstAppearingOnce()
    {
        for(int i = 0; i < s.length(); i++){
            if(map.get(s.charAt(i)) == 1)
                return s.charAt(i);
        }
        return '#';
    }
}