【面试题54-字符流中第一个不重复的字符】

剑指offer第五十四题。

题目描述

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

解题思路

常规的解法是用一个map来存储，这样空间复杂度为O(n)，然后每次都遍历map获取第一个不重复的字符，时间复杂度也为O(n)。下面显示i代码：

import java.util.Map;
import java.util.LinkedHashMap;
public class Solution {
    //用有序的Map：LinkedHashMap来存放char，并且记录其出现次数
    Map<Character,Integer> map = new LinkedHashMap<Character,Integer>();
    //Insert one char from stringstream
    public void Insert(char ch)
    {
        if(!map.containsKey(ch)){
            map.put(ch,1);
        }else{
            map.put(ch,map.get(ch)+1);
        }
    }
  //return the first appearence once char in current stringstream
    public char FirstAppearingOnce()
    {
        for(char ch:map.keySet()){
            int count = map.get(ch);
            //目前第一个只出现一次的字符，返回
            if(count == 1)
                return ch;
        }
        return '#';
    }
}

这种很容易想到，但是能不能再优化一点呢？我们知道，ASCII码一共只有128个字符，那么我可以直接定义一个长度为128的数组，空间复杂度为O(n)，时间复杂度控制在常数级别，虽然我获取第一个只出现一次的元素需要一个while循环，但是这个循环不可能超过128，一般很快就可以拿到。

我的答案

import java.util.LinkedList;
public class Solution {
    //英文字符不会逃出128个ascii码的范围，所以定义这个长度的数组
    //第一个ASCII码是一个空字符，所以我都是相对于` `进行一一排列
    //比如数字'0'是30，那'0'-''等于30，就存在tmp[30]这个地方即可
    //注意，tmp存的是出现的子树，即'0'出现了两次，那么tmp[30]就是2
    int[] tmp = new int[128];
    //维护一个队列，只保存一次进来的元素，重复的丢掉
    LinkedList<Character> queue = new LinkedList<>();
    //Insert one char from stringstream
    public void Insert(char ch)
    {
        //第一次进来的元素放进队列尾部
        if(tmp[ch-' '] == 0){
            queue.add(ch);
        }
        //进来一次，就对相应坐标加一，统计出出现次数
        tmp[ch-' ']++;
    }
  //return the first appearence once char in current stringstream
    public char FirstAppearingOnce()
    {
        //取得时候是从队列得头部取，因为头部是比较早的数据
        //出现次数大于等于2的话就不断丢弃，知道找到第一个出现次数为1的字符跳出循环
        while(!queue.isEmpty() && tmp[queue.getFirst()-' ']>=2){
            queue.removeFirst();
        }
        
        //拿到这个第一个只出现一次的字符
        if(!queue.isEmpty()){
            return queue.getFirst();
        }
        
        //拿不到了，说明没有只出现一次的字符，那么就返回#
        return '#';
    }
}