剑指offer----字符流中第一个不重复的字符----java实现

来源:互联网 发布:使用itunes更新软件 编辑:IT博客网 时间:2019/10/18 02:27

题目描述

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

思路:第一个不重复的字符  两个关键点 不重复也就是出现一次,第一个也就是找到将其返回不再找下面的了

两个辅助空间

(1)HashMap根据字符放入map中每次将次数加1

(2)ArrayList将插入的每个字符放入到list中,list是有顺序地存放。遍历listmap中根据字符找其出现的次数。

import java.util.ArrayList;import java.util.HashMap;public class First{HashMap<Character,Integer> map = new HashMap<Character,Integer>();//存放字符和其出现的次数ArrayList<Character> list = new ArrayList<Character>();//存放字符//把字符存对应的次数在map中更新,并把字符按照出现顺序存放在list中public void Insert(char ch)    { //判断map中是否已经包含要插入的字符,如果已经包含则将其次数+1      if(map.containsKey(ch))      {     map.put(ch,map.get(ch)+1);//map.get(ch)是根据key得到value的值      }      else      {      map.put(ch,1);//如果map中还没有包含,则把ch放入map中,并将其值设为1;      }      list.add(ch);//将ch放入list中,便于根据list中保存的ch到map中去查询出现次数    }//遍历list去map中寻找出现的次数    public char FirstAppearingOnce()    {    char ch ='#';      for (int i = 0; i < list.size(); i++)  {if(map.get(list.get(i)) == 1){ch = list.get(i);break;}  }      return ch;    }}


0 0