剑指offer—字符流中第一个不重复的字符 解答

剑指offer—字符流中第一个不重复的字符

题目描述

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

如果当前字符流没有存在出现一次的字符,返回#字符。

思路

  • 借助辅助空间保存字符出现的次数

总的字符一共256个,建立一个256个空间大小的数组,对应char的位置保存当前char出现的次数

用一个String保存输入的整个字符串

循环字符串每个字符,去数组中查找出现次数,如果存在为1的就返回该字符,否则返回#

代码

public class Solution {
   //Insert one char from stringstream
    String s = "";
    int []chars = new int [256];
    public void Insert(char ch){
        s += ch;
        chars[ch] ++;
    }
  //return the first appearence once char in current stringstream
    public char FirstAppearingOnce(){
        for(char c:s.toCharArray()){
            if(chars[c]==1) return c;
        }
        return '#';
    }
}