方法一: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) }