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

傷城~ 2022-09-23 10:48 146阅读 0赞

## 题目描述 ##

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

##### 输出描述: #####

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

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

两个辅助空间

（1）HashMap 根据字符放入map中每次将次数加1；

（2）ArrayList 将插入的每个字符放入到list中，list是有顺序地存放。遍历list去map中根据字符找其出现的次数。

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;
    	    }
    }