题目描述

请实现一个函数用来找出字符流中第一个只出现一次的字符。例如，当从字符流中只读出前两个字符"go"时，第一个只出现一次的字符是"g"。当从该字符流中读出前六个字符“google"时，第一个只出现一次的字符是"l"。
后台会用以下方式调用Insert 和 FirstAppearingOnce 函数

string caseout = "";
1.读入测试用例字符串casein
2.如果对应语言有Init()函数的话，执行Init() 函数
3.循环遍历字符串里的每一个字符ch {
Insert(ch);
caseout += FirstAppearingOnce()
}
2. 输出caseout，进行比较。

返回值描述：

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

示例1

输入：
"google"

返回值
"ggg#ll"

从题已知信息

  1. 需要统计每个字符出现的次数

  2. 每次返回只出现一次的字符

  3. 如果没有只出现一次的字符返回 '#'

    方法一: 哈希法 + 队列

    思路和算法

    针对题目的描述，我们需要解决下面几个问题

  4. 用什么数据结构来保存一个字符并切统计出现次数？

    1. 这个问题可以用 HashMap 来做

  5. 怎么保证每次返回的是最小的数字？

    1. 需要使用一个队列来维护最小的数组

通过以上问题，我们可以考虑用 HashMap + LinkedList 来做，或者用 LinkedHashMap

全部代码如下：

import java.util.*;

public class Solution {
    // 用map来存储，并且LinkedHashMap 是有序的
    Map<Character, Integer> map = new LinkedHashMap<>();

    public void Insert(char ch) {
         // 统计每个字符的字数
        map.put(ch, map.getOrDefault(ch, 0) + 1);
    }

    public char FirstAppearingOnce() {
        for (char c : map.keySet()) {
            //LinkedHashMap是有顺的，找到的第一个为1的
            if (map.get(c) == 1)
                return c;
        }
        return '#';
    }

}

复杂度分析

时间复杂度：Insert 是 O(1) FirstAppearingOnce 是 O(1)， 字符最多128个，常数级遍历
空间复杂度：O(1), map大小不会超过128