JZ75 字符流中第一个不重复的字符

题目

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

 


 


 


 


 


 

，第一个只出现一次的字符是"l"












。

方法1 使用LinkedHashMap

思路

算法实现

LinkedHashMap实现顺序插入 
 
 
 
 
 
 ，不过查询速度会比较慢 具体做法： step 1：用哈希表统计每个字符的次数 
   
   
   
   
   
   
，是全局变量  
  
  
  
  
  
 。 step 2：在Insert函数中对输入的字符
 

 

 

 

 

 
，然后统计出现次数 
  
  
  
  
  
  。 step 3：在FirstAppearingOnce函数遍历该字符串
 

 

 

 

 

 

 ，对于每个字符查找哈希表            ，返回第一个计数为1的字符 

 
 

 
 

 
 

 
 

 
 

 
 
，则返回#


 


 


 


 


 


 

。

代码

package mid.JZ75字符流中第一个不重复的字符; import java.util.HashMap; import java.util.LinkedHashMap; import java.util.Map; public class Solution { Map<Character,Integer> map = new LinkedHashMap<>(); //Insert one char from stringstream public void Insert(char ch) { map.put(ch, map.getOrDefault(ch, 0) + 1); } //return the first appearence once char in current stringstream /** * LinkedHashMap实现顺序插入












，不过查询速度会比较慢 * 运行时间 165ms * 占用内存 15860KB * @return */ public char FirstAppearingOnce() { for (Character character : map.keySet()) { if (map.get(character) == 1) { return character; } } return #; } }

方法2 哈希表+字符串（推荐使用）

思路

算法实现

又是一个找到是否重复的问题 
 
 
 
 
 
。我们还是可以用哈希表来记录各个字符出现的次数                   ， 根据这样只要是字符串最前面且哈希表中次数为1的字符就是我们要找的  
   
   
   
   
   
   。 具体做法： step 1：准备一个字符串来记录输入的字符流 
 
 
 
 
 
 
 
 
 
 
 
 
，用哈希表统计每个字符的次数


















，二者都是全局变量

 

 

 

 

 

 
。 step 2：在Insert函数中对输入的字符             ，加到字符串最后 
  
 
  
 
  
 
  
 
  
 
  
 
，然后统计出现次数
 

 

 

 

 

 

。 step 3：在FirstAppearingOnce函数遍历该字符串












，对于每个字符查找哈希表 
  
  
  
  
  
  ，返回第一个计数为1的字符 
  
  
  
  
  
  
， 如果遍历完字符串以后都没

 


 


 


 


 


 

，则返回#             。

代码

package mid.JZ75字符流中第一个不重复的字符; import java.util.HashMap; import java.util.Map; public class Solution2 { StringBuilder sb = new StringBuilder(); Map<Character,Integer> map = new HashMap<>(); //Insert one char from stringstream public void Insert(char ch) { sb.append(ch); map.put(ch, map.getOrDefault(ch, 0) + 1); } //return the first appearence once char in current stringstream /** * 运行时间 13ms * 占用内存 9952KB * @return */ public char FirstAppearingOnce() { for (int i = 0; i < sb.length(); i++) { if (map.get(sb.charAt(i)) == 1) { return sb.charAt(i); } } return #; } }

方法3 哈希表+字符串（推荐使用）

思路

算法实现

除了使用字符串记录字符流 
 
 
 
 
 
 ，还可以用队列记录字符流 
   
   
   
   
   
   
，每次插入的时候
 

 

 

 

 

 
，只需要将第一次出现的字符加入到队列中
 

 

 

 

 

 

 ，然后正常计数
 

 
 

 
 

 
 

 
 

 
 

 
 。 查找第一个不重复出现的字符的时候            ，从队首开始查询哈希表 

 
 

 
 

 
 

 
 

 
 

 
 
， 如果出现次数为1












，则返回该字符                   ，如果不为1 
 
 
 
 
 
 
 
 
 
 
 
 
，则从队首将其弹出












。 具体做法： step 1：准备一个队列来记录输入的字符流


















，用哈希表统计每个字符的次数             ，二者都是全局变量                   。 step 2：在Insert函数中对输入的字符 
  
 
  
 
  
 
  
 
  
 
  
 
，加到队列最后












，然后统计出现次数
 
 
 
 
 
 
 
 
 
 
 
 
 。 step 3：在FirstAppearingOnce函数中 
  
  
  
  
  
  ，不断检查队首元素直到队列为空 
  
  
  
  
  
  
，队首出现次数为1次

 


 


 


 


 


 

，就返回 
 
 
 
 
 
 ， 队首出现次数不为1就弹出


















。 
   
   
   
   
   
   
，则返回#             。

代码

package mid.JZ75字符流中第一个不重复的字符; import java.util.HashMap; import java.util.LinkedList; import java.util.Map; import java.util.Queue; public class Solution3 { Queue<Character> queue = new LinkedList<>(); Map<Character,Integer> map = new HashMap<>(); //Insert one char from stringstream public void Insert(char ch) { if (!map.containsKey(ch)) { queue.offer(ch); } map.put(ch, map.getOrDefault(ch, 0) + 1); } //return the first appearence once char in current stringstream /** * 运行时间 15ms * 占用内存 9972KB * @return */ public char FirstAppearingOnce() { while(!queue.isEmpty()) { if (map.get(queue.peek()) == 1) { return queue.peek(); } else { queue.poll(); } } return #; } }