題⽬描述

請實現⼀個函數⽤來找出字符流中第⼀個只出現⼀次的字符。例如，當從字符流中只讀出前兩個字符" go "時，第⼀個只出現⼀次的字符是" g "。當從該字符流中讀出前六個字符“ google "時，第⼀個只出現⼀次的字符是" l "。

返回值描述：如果當前字符流沒有存在出現⼀次的字符，返回 # 字符。

思路及解答

有序哈希表

可以直接使用哈希的數據結構來存取我們的字符，對與重複的字符可以對值進行統計或者標記都行。這裏要用LinkedHashMap，因為題目要求到了要出現的第一個不重複的字符，所以如果不使用有序map的話，那麼我們就不能保證取到的是第一個不重複的字符。

public class Solution {
    //Insert one char from stringstream
    //因為後面要遍歷保證有序，所以這裏使用LinkedHashMap
    Map<Character,Integer> map = new LinkedHashMap<>();
    
    public void Insert(char ch){
        if(map.containsKey(ch)){
            map.put(ch,-1);
        }else{
            map.put(ch,1);
        }
    }
  //return the first appearence once char in current stringstream
    public char FirstAppearingOnce(){
        for(Character i : map.keySet()){
            if(map.get(i) == 1){
                return i;
            }
        }
        return '#';
    }
}

• 時間複雜度：插入O(1)，查詢最壞O(n)
• 空間複雜度：O(n)

隊列+計數數組(最優)

結合了隊列的先進先出特性和數組的快速訪問能力，能夠高效解決動態字符流中的首個不重複字符查找問題

public class Solution {
    private int[] count = new int[128];  // ASCII字符計數數組
    private Queue<Character> queue = new LinkedList<>();  // 維護候選字符順序
    
    // 插入字符到流中
    public void Insert(char ch) {
        count[ch]++;  // 字符出現次數加1
        queue.add(ch);  // 字符加入隊列
        
        // 清理隊列頭部已重複的字符
        while (!queue.isEmpty() && count[queue.peek()] > 1) {
            queue.poll();
        }
    }
    
    // 返回當前第一個不重複字符
    public char FirstAppearingOnce() {
        return queue.isEmpty() ? '#' : queue.peek();
    }
}

• 時間複雜度：每個字符的插入操作是均攤O(1)，查詢操作是嚴格的O(1)
• 空間複雜度：O(1)（固定大小的數組和隊列）

雙數組記錄

通過記錄字符首次出現的位置和狀態，在查詢時進行全局掃描

public class Solution {
    private int[] position = new int[128];  // 記錄字符位置或狀態
    private int index = 1;  // 當前字符位置索引
    
    public Solution() {
        // 初始化，-1表示未出現過
        for (int i = 0; i < 128; i++) {
            position[i] = -1;
        }
    }
    
    public void Insert(char ch) {
        if (position[ch] == -1) {
            // 第一次出現，記錄位置
            position[ch] = index;
        } else if (position[ch] > 0) {
            // 重複出現，標記為-2
            position[ch] = -2;
        }
        index++;
    }
    
    public char FirstAppearingOnce() {
        int minIndex = Integer.MAX_VALUE;
        char result = '#';
        
        // 掃描找到最小正整數值對應的字符
        for (int i = 0; i < 128; i++) {
            if (position[i] > 0 && position[i] < minIndex) {
                minIndex = position[i];
                result = (char) i;
            }
        }
        return result;
    }
}

• 時間複雜度：插入O(1)，查詢O(1)（固定128次循環）
• 空間複雜度：O(1)