41.2 字符流中第一个不重复的字符

题目描述

请实现一个函数用来找出字符流中第一个只出现一次的字符。例如，当从字符流中只读出前两个字符“go”时，第一个只出现一次的字符是“g”。当从该字符流中读出前六个字符“google”时，第一个只出现一次的字符是“l”。

解题思路

使用统计数组来统计每个字符出现的次数，本题涉及的字符都是 ASCII 码，因此使用一个大小为 128 的整型数组就能完成次数统计任务。

使用队列按到达顺序存储第一次出现的字符，并在每次有新的字符从字符流到达时移除队列头部那些出现次数不再是一次的元素。重复出现的字符不再入队，队列最多保存 128 个字符。因为队列是先进先出顺序，因此队列头部的元素就是第一个只出现一次的字符。

private int[] cnts = new int[128];
private Queue<Character> queue = new LinkedList<>();

public void Insert(char ch) {
    if (++cnts[ch] == 1)
        queue.add(ch);
    while (!queue.isEmpty() && cnts[queue.peek()] > 1)
        queue.poll();
}

public char FirstAppearingOnce() {
    return queue.isEmpty() ? '#' : queue.peek();
}