题解 | #字符流中第一个不重复的字符#

【问题描述】

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

【解题思路】

• 使用统计数组来统计每个字符出现的次数，本题涉及到的字符都是ASCII码，
• 因此大小为 128 的整型数组就能完成统计任务。
• 使用队列来存储达到的字符，并在每次有新的字符从字符流到达时移除队列头部那些出现次数不再是一次的元素。
• 因为队列是先进先出顺序，因此因此队列头部元素为第一次只出现一次的字符。

【代码示例】

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

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

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