剑指offer-54、字符流中第一个不重复的字符

题⽬描述

请实现⼀个函数⽤来找出字符流中第⼀个只出现⼀次的字符。例如，当从字符流中只读出前两个字符" go "时，第⼀个只出现⼀次的字符是" g "。当从该字符流中读出前六个字符“ google "时，第⼀个只出现⼀次的字符是" l "。
返回值描述：如果当前字符流没有存在出现⼀次的字符，返回 # 字符。
思路及解答

有序哈希表

可以直接使用哈希的数据结构来存取我们的字符，对与重复的字符可以对值进行统计或者标记都行。这里要用LinkedHashMap，因为题目要求到了要出现的第一个不重复的字符，所以如果不使用有序map的话，那么我们就不能保证取到的是第一个不重复的字符。

1. public class Solution {
2.     //Insert one char from stringstream
3.     //因为后面要遍历保证有序，所以这里使用LinkedHashMap
4.     Map<Character,Integer> map = new LinkedHashMap<>();
5.    
6.     public void Insert(char ch){
7.         if(map.containsKey(ch)){
8.             map.put(ch,-1);
9.         }else{
10.             map.put(ch,1);
11.         }
12.     }
13.   //return the first appearence once char in current stringstream
14.     public char FirstAppearingOnce(){
15.         for(Character i : map.keySet()){
16.             if(map.get(i) == 1){
17.                 return i;
18.             }
19.         }
20.         return '#';
21.     }
22. }

复制代码

• 时间复杂度：插入O(1)，查询最坏O(n)
  
• 空间复杂度：O(n)
  

队列+计数数组(最优)

结合了队列的先进先出特性和数组的快速访问能力，能够高效解决动态字符流中的首个不重复字符查找问题

1. public class Solution {
2.     private int[] count = new int[128];  // ASCII字符计数数组
3.     private Queue<Character> queue = new LinkedList<>();  // 维护候选字符顺序
4.    
5.     // 插入字符到流中
6.     public void Insert(char ch) {
7.         count[ch]++;  // 字符出现次数加1
8.         queue.add(ch);  // 字符加入队列
9.         
10.         // 清理队列头部已重复的字符
11.         while (!queue.isEmpty() && count[queue.peek()] > 1) {
12.             queue.poll();
13.         }
14.     }
15.    
16.     // 返回当前第一个不重复字符
17.     public char FirstAppearingOnce() {
18.         return queue.isEmpty() ? '#' : queue.peek();
19.     }
20. }

复制代码

• 时间复杂度：每个字符的插入操作是均摊O(1)，查询操作是严格的O(1)
  
• 空间复杂度：O(1)（固定大小的数组和队列）
  

双数组记录

通过记录字符首次出现的位置和状态，在查询时进行全局扫描

1. public class Solution {
2.     private int[] position = new int[128];  // 记录字符位置或状态
3.     private int index = 1;  // 当前字符位置索引
4.    
5.     public Solution() {
6.         // 初始化，-1表示未出现过
7.         for (int i = 0; i < 128; i++) {
8.             position[i] = -1;
9.         }
10.     }
11.    
12.     public void Insert(char ch) {
13.         if (position[ch] == -1) {
14.             // 第一次出现，记录位置
15.             position[ch] = index;
16.         } else if (position[ch] > 0) {
17.             // 重复出现，标记为-2
18.             position[ch] = -2;
19.         }
20.         index++;
21.     }
22.    
23.     public char FirstAppearingOnce() {
24.         int minIndex = Integer.MAX_VALUE;
25.         char result = '#';
26.         
27.         // 扫描找到最小正整数值对应的字符
28.         for (int i = 0; i < 128; i++) {
29.             if (position[i] > 0 && position[i] < minIndex) {
30.                 minIndex = position[i];
31.                 result = (char) i;
32.             }
33.         }
34.         return result;
35.     }
36. }

复制代码

• 时间复杂度：插入O(1)，查询O(1)（固定128次循环）
  
• 空间复杂度：O(1)
  

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！

过来提前占个楼