[编程题]字符流中第一个不重复的字符

思路分析

1、Insert方法的作用
我们在每次插入一个字符char的时候，就把其累加到字符串input上，并且借助map比较这个字符串是否已经存在于map中（map的key是字符串，value是这个字符串出现的次数）

• 如果本身map中无这样一个key,就把key设置进去，且value=1
• 如果本身map中有这样一个key,就把key更新，在原来的次数上加1；

2、FirstAppearingOnce方法

• 我们先造一个ArrayList筛选存储map中出现的次数为1（即value=1）的key
• 借助拿到的每一个出现1次的key，借助原始输入的字符合并成的字符串，判断该key出现在字符串的位置。
  • 如果该字符的索引最小，那么这个值就是需要返回的值、

完整代码如下：

import java.util.*;

public class Solution {
     String input = "";
     HashMap<Character,Integer> map = new HashMap<>();

    //把插入的值放入到input串中，并把次数记录在hashMap中
    //Insert one char from stringstream
    public void Insert(char ch)
    {
        Set keys = map.keySet();
        boolean contains = keys.contains(ch);
        //如果map中没这个键，就加入
        if (!contains){
            map.put(ch,1);//指定该键是ch,值是1
            input += ch;
        }else {
            int value = map.get(ch);
            value++;
            map.put(ch,value);  //之前有这个key的话就更新
            input += ch;
        }
    }

    //思想：把map中出现次数是1的结果拿如list中，借助input的输入的string,筛选出最前边的字符
    //return the first appearence once char in current stringstream
    public char FirstAppearingOnce(){
        //暂存结果
        ArrayList<Character> lis = new ArrayList<>();
        //筛选出出现1次的信息放入list
        for(Map.Entry<Character,Integer> entry:map.entrySet()){
            char key = entry.getKey();
            Integer value = entry.getValue();
            if (value==1){
                lis.add(key);
            }
        }

        //因为集合map是无序的，索引我们需要借助input字符串来确定哪个字符出现1次且在最前边
        int minIndex = Integer.MAX_VALUE;//默认是一个很大的索引值
        if (lis.isEmpty()){
            return '#';
        }else {
            for (int i = 0; i < lis.size(); i++) {
                int index = input.indexOf(lis.get(i));
                if (index<minIndex){
                    minIndex = index;
                }
            }
            return input.toCharArray()[minIndex];
        }
    }
}