字符流中第一个不重复的字符【Java版】

方法一：LinkedHashMap <Character, Integer>

import java.util.LinkedHashMap;
//必须要用LinkedHashMap，不能用HashMap/Map //因为LinkedHashMap的有序性(要求返回第一个char)

public class Solution {
    LinkedHashMap <Character, Integer> map = new LinkedHashMap <Character, Integer>();
    //空间O(N), N为字符类型数量，小于100

    // (1) Insert one char from stringstream
    public void Insert(char ch){//这里的意思应该是多次调用Insert函数，每次插入一个char
        if(map.containsKey(ch)){
            map.put(ch,map.get(ch)+1);
        }
        else map.put(ch,1);
    }//时间O(N), N为字符类型数量，小于100   空间O(1)

    // (2) return the first appearence once char in current stringstream
    public char FirstAppearingOnce(){//这个函数和上面的函数任意独立穿插调用使用
        for(char ch:map.keySet()){//.keySet()获取map里面所有的key
            if(map.get(ch) == 1)return ch;
        }
        return '#';
    }//时间O(N), N为字符类型数量，小于100   空间O(1)
}

方法二（高效）：int[128]存次数 + Queue< Character>

import java.util.LinkedList;

public class Solution {
    int[] count = new int[128];//ASCII
    LinkedList<Character> queue = new LinkedList<Character>();//注意add/remove的使用
    //空间O(N)

    public void Insert(char ch){
        if(++count[ch]==1)queue.add(ch);
    }//时间O(1) 空间O(1)

    public char FirstAppearingOnce(){
        while(queue.peek() != null){
            if(count[queue.peek()]>1)queue.remove();//重复了就移出队列，它不会再回来了
            else return queue.peek();
        }
        return '#';
    }//时间O(N) 如果FirstAppearingOnce()量大的话，可以接近O(1)   //空间O(1)
}