剑指Offer（五十四）-- 字符流中第一个不重复的字符

Github仓库地址：https://github.com/Damaer/CodeSolution 笔记地址：https://damaer.github.io/CodeSolution/ 仓库介绍：刷题仓库：CodeSolution

题目描述

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

返回值描述:如果当前字符流没有存在出现一次的字符，返回#字符。

思路以及解答

这道题有两个函数要求实现，主要是输入函数和输出函数，一个是读入新的字符，另外一个是输出第一个只出现一次的字符。

我的做法是借助一个数组和一个队列，数组中是存储了元素出现的次数，会不断的往上面叠加，字母一般128个就足够了。队列的话，主要是存储元素出现的顺序。

添加元素的函数：

判断计数数组里面，字符出现的个数是不是为0，为0则往队列里面添加元素，如果不为0，添加了没有意义，说明包括当前出现的至少出现了两次。同时更新计数器。

查找第一个只出现一次的字符判断队列里面是否为空，取出第一个元素，不为空的时候，判断计数器里面该字符出现的次数是不是为1，为1的时候直接返回该字符，如果不是1，那么直接把该字符从队列里面移除，说明出现不止一次了。直到队列为空，返回“#”。

import java.util.Queue;
import java.util.LinkedList;
import java.lang.Character;

public class Solution {
    int[] charCount = new int[128];
    Queue<Character> queue = new LinkedList<Character>();

    // 模拟输入字符
    public void Insert(char ch) {
        if (charCount[ch] == 0) {
            queue.add(ch);
        }
        charCount[ch]++;
    }

    // 模拟输出第一个只出现一次的字符
    public char FirstAppearingOnce() {
        Character character = null;
        char c = 0;
        // 取出队列的第一个
        while ((character = queue.peek()) != null) {
            // 取出里面的字符
            c = character.charValue();
            // 判断个数是不是为1
            if (charCount[c] == 1) {
                return c;
            }
            else {queue.remove();}
        }
        return '#';
    }
}

时间复杂度为O(n)，空间复杂度也为O(n)。

【作者简介】：

秦怀，公众号【秦怀杂货店】作者，技术之路不在一时，山高水长，纵使缓慢，驰而不息。个人写作方向：Java源码解析，JDBC，Mybatis，Spring，redis，分布式，剑指Offer，LeetCode等，认真写好每一篇文章，不喜欢标题党，不喜欢花里胡哨，大多写系列文章，不能保证我写的都完全正确，但是我保证所写的均经过实践或者查找资料。遗漏或者错误之处，还望指正。

平日时间宝贵，只能使用晚上以及周末时间学习写作 - END -