本文共 2389 字，大约阅读时间需要 7 分钟。

题目描述

请实现一个函数用来找出字符流中第一个只出现一次的字符。例如，当从字符流中只读出前两个字符”go”时，第一个只出现一次的字符是”g”。当从该字符流中读出前六个字符“google”时，第一个只出现一次的字符是”l”。 如果当前字符流没有存在出现一次的字符，返回#字符。

分析

思路1：在文章曾提到一种思路，利用LinkedHashMap，可以保持输出顺序和输入顺序（也可以是自定义顺序）一致，记录字符或者数字及其出现的次数，在$O(1)$内找到出现1测的目标。

这里同样可以借鉴之前的思路，使用LinkedHashMap保存字符及其出现的次数，使用ArrayList保存字符流。

牛客AC：

import java.util.Map;import java.util.LinkedHashMap;import java.util.List;import java.util.ArrayList;public class Solution {
       // Map存放字符及其出现的次数    Map
   
     map = new LinkedHashMap
    
     ();    // List存放字符流序列    List
     
       list = new ArrayList
      
       ();    // Insert one char from stringstream    public void Insert(char ch) {        if (map.containsKey(ch))             map.put(ch, map.get(ch) + 1);   // map 会覆盖重复元素，更新重复key的最新value        else             map.put(ch, 1);        list.add(ch);    }    // return the first appearence once char in current stringstream    public char FirstAppearingOnce() {        char c = '#';        for (char key : list) {            if (map.get(key) == 1) {                c = key;                break;            }        }        return c;    }}
      
     
    
   

思路2：所有的字符总数为256。利用一个int型数组存储ASCII码为i的字符第一次出现的索引，这个数组初值置为-1。每读一个字符，将该字符的位置存入字符ASCII码（0-255）对应的数组下标中。若值为-1，表示第一次读入，不为-1且大于0表示不是第一次读入，将值改为-2（重复多次读入）。全部处理完成后，int数组中的值，-1的是没有出现的字符，-2是重复多次出现的字符，大于0的就是只出现一次的字符，而且元素的值是该字符第一次出现的索引。找到大于0的最小值，那它就是第一个只出现一次的字符的ASCII值，将ASCII值转为字符即可。

牛客AC：

public class Solution {
       private int[] occurrence = new int[256];    // 存储ASCII码为i的字符第一次出现的索引    private int index = 0;      // 字符在整个字符流中的索引    // 初始置为-1，所有字符均没有出现    public Solution() {        for(int i = 0; i < 256; i++)            occurrence[i] = -1;    }    // 从字符流读取一个字符，插入到数组中    public void Insert(char ch) {        if(occurrence[ch] == -1)    // 该字符没有出现过，存储它在字符流中的索引            occurrence[ch] = index;        else if(occurrence[ch] >= 0)    // 该字符出现过，索引置为-2            occurrence[ch] = -2;        index++;    }    // 获取第一个出现一次的字符    // 数组中元素值大于等于0的最小值，是第一个只出现一次的字符    public char FirstAppearingOnce() {        char ch = '#';        int minIndex = Integer.MAX_VALUE;        for(int i = 0; i < 256; i++) {            int tmpOccurrence = occurrence[i];            if(tmpOccurrence >= 0 && tmpOccurrence < minIndex) {                ch = (char) i;                minIndex = occurrence[i];            }        }        return ch;    }}

参考

转载地址：http://jkxgi.baihongyu.com/