校招算法笔面试 | 字符流中第一个不重复的字符

题目

题目链接
题目标重要信息：

• 实现一个函数用来找出字符流中第一个只出现一次的字符
  
• Insert函数插入字符流的下一个字符， FirstAppearingOnce找到第一个不重复出现的字符
  
• 假如找不到返回#
  
• 字符串中出现的字符一定在 ASCII 码内
  

闻一知十：

学习完本题的思绪你可以办理如下题目：
JZ50. 第一个只出现一次的字符
JZ39. 数组中出现次数超过一半的数字
JZ56. 数组中只出现一次的两个数字
方法一：哈希表+字符串（推荐利用）

知识点：哈希表
哈希表是一种根据关键码（key）直接访问值（value）的一种数据布局。而这种直接访问意味着只要知道key就能在                                   O                         (                         1                         )                              O(1)                  O(1)时间内得到value，因此哈希表常用来统计频率、快速查验某个元素是否出现过等。
思绪：
又是一个找到是否重复的题目。我们还是可以用哈希表来记录各个字符出现的次数，根据这样只要是字符串最前面且哈希表中次数为1的字符就是我们要找的。
具体做法：

• step 1：预备一个字符串来记录输入的字符流，用哈希表统计每个字符的次数，二者都是全局变量。
  
• step 2：在Insert函数中对输入的字符，加到字符串末了，然后统计出现次数。
  
• step 3：在FirstAppearingOnce函数遍历该字符串，对于每个字符查找哈希表，返回第一个计数为1的字符，假如遍历完字符串以后都没，则返回#。
  

Java实当代码：

1. import java.util.*;
2. public class Solution {
3.     private StringBuilder s = new StringBuilder();
4.     private HashMap<Character, Integer> mp = new HashMap<>();
5.     //Insert one char from stringstream
6.     public void Insert(char ch)
7.     {
8.         //插入字符
9.         s.append(ch);  
10.         //哈希表记录字符出现次数
11.         mp.put(ch, mp.getOrDefault(ch, 0) + 1);
12.     }
13.     //return the first appearence once char in current stringstream
14.     public char FirstAppearingOnce()
15.     {
16.         //遍历字符串
17.         for(int i = 0; i < s.length(); i++)
18.             //找到第一个出现次数为1的
19.             if(mp.get(s.charAt(i)) == 1)
20.                 return s.charAt(i);
21.         //没有找到
22.         return '#';
23.     }
24. }

复制代码

C++实当代码：

1. class Solution
2. {
3. public:
4.     unordered_map<char, int> mp;
5.     //记录输入的字符串
6.     string s;
7.     //Insert one char from stringstream
8.     void Insert(char ch) {
9.         //插入字符
10.         s += ch;  
11.         //哈希表记录字符出现次数
12.         mp[ch]++;
13.     }
14.     //return the first appearence once char in current stringstream
15.     char FirstAppearingOnce() {
16.         //遍历字符串
17.         for(int i = 0; i < s.length(); i++)
18.             //找到第一个出现次数为1的
19.             if(mp[s[i]] == 1)
20.                 return s[i];
21.         //没有找到
22.         return '#';
23.     }
24. };

复制代码

Python实当代码：

1. class Solution:
2.     def __init__(self):
3.         self.s = ""
4.         self.mp = dict()
5.         
6.     def FirstAppearingOnce(self):
7.         #遍历字符串
8.         for c in self.s:
9.             #找到第一个出现次数为1的
10.             if self.mp[c] == 1:
11.                 return c
12.         #没有找到
13.         return '#'
14.         
15.     def Insert(self, char):
16.         #插入字符
17.         self.s += char  
18.         #哈希表记录字符出现次数
19.         if char in self.mp:
20.             self.mp[char] += 1
21.         else:
22.             self.mp[char] = 1

复制代码

复杂度分析：

• 时间复杂度：                                        O                            (                            n                            )                                  O(n)                     O(n)，每次插入字符都是                                        O                            (                            1                            )                                  O(1)                     O(1)，每次查询必要遍历字符串                                        O                            (                            n                            )                                  O(n)                     O(n)
  
• 空间复杂度：                                        O                            (                            n                            )                                  O(n)                     O(n)，字符一定在ASCII范围内，因此哈希表大小为常数，但是记录的字符串长度为还是为                                        n                                  n                     n
  

方法二：哈希表+队列（扩展思绪）

知识点：队列
队列是一种仅支持在表尾举行插入利用、在表头举行删除利用的线性表，插入端称为队尾，删除端称为队首，因团体类似排队的队伍而得名。它满足先辈先出的性子，元素入队即将新元素加在队列的尾，元素出队即将队首元素取出，它后一个作为新的队首。
思绪：
除了利用字符串记录字符流，还可以用队列记录字符流，每次插入的时间，只必要将第一次出现的字符加入到队列中，然后正常计数。
查找第一个不重复出现的字符的时间，从队首开始查询哈希表，假如出现次数为1，则返回该字符，假如不为1，则从队首将其弹出，因为反正后续也不可能是这个已经重复的字符了。
具体做法：

• step 1：预备一个队列来记录输入的字符流，用哈希表统计每个字符的次数，二者都是全局变量。
  
• step 2：在Insert函数中对输入的字符，加到队列末了，然后统计出现次数。
  
• step 3：在FirstAppearingOnce函数中，不断检查队首元素直到队列为空，队首出现次数为1次，就返回，队首出现次数不为1就弹出。
  

图示：

Java实当代码：

1. import java.util.*;
2. public class Solution {
3.     private Queue<Character> q = new LinkedList<>();
4.     private HashMap<Character, Integer> mp = new HashMap<>();
5.     //Insert one char from stringstream
6.     public void Insert(char ch)
7.     {
8.         //插入字符
9.         if(!mp.containsKey(ch))
10.             q.offer(ch);
11.         //哈希表记录字符出现次数
12.         mp.put(ch, mp.getOrDefault(ch, 0) + 1);
13.     }
14.     //return the first appearence once char in current stringstream
15.     public char FirstAppearingOnce()
16.     {
17.         while(!q.isEmpty()){
18.             //第一个不重复的字符
19.             if(mp.get(q.peek()) == 1)
20.                 return q.peek();
21.             //弹出前面的已经重复的字符
22.             else
23.                 q.poll();
24.         }
25.         //都重复了
26.         return '#';
27.     }
28. }

复制代码

C++实当代码：

1. class Solution
2. {
3. public:
4.     unordered_map<char, int> mp;
5.     queue<char> q;
6.     //Insert one char from stringstream
7.     void Insert(char ch) {
8.         //第一次出现加入队列中
9.         if(mp.find(ch) == mp.end())
10.             q.push(ch);
11.         //哈希表记录字符出现次数
12.         mp[ch]++;
13.     }
14.     //return the first appearence once char in current stringstream
15.     char FirstAppearingOnce() {
16.         while(!q.empty()){
17.             //第一个不重复的字符
18.             if(mp[q.front()] == 1)
19.                 return q.front();
20.             //弹出前面的已经重复的字符
21.             else
22.                 q.pop();
23.         }
24.         //都重复了
25.         return '#';
26.     }
27. };

复制代码

Python实当代码：

1. class Solution:
2.     def __init__(self):
3.         self.q = []
4.         self.mp = dict()
5.         
6.     def FirstAppearingOnce(self):
7.         while len(self.q) != 0:
8.             #第一个不重复的字符
9.             if self.mp[self.q[0]] == 1:
10.                 return self.q[0]
11.             #弹出前面的已经重复的字符
12.             else:
13.                 self.q.pop(0)
14.         #都重复了
15.         return '#'
16.         
17.     def Insert(self, char):
18.         #哈希表记录字符出现次数
19.         if char in self.mp:
20.             self.mp[char] += 1
21.         else:
22.             self.mp[char] = 1
23.             #插入字符
24.             self.q.append(char)

复制代码

复杂度分析：

• 时间复杂度：                                        O                            (                            n                            )                                  O(n)                     O(n)，每次插入字符都是                                        O                            (                            1                            )                                  O(1)                     O(1)，每次查询均匀复杂度比方法一下降了，但是最坏必要遍历队列                                        O                            (                            n                            )                                  O(n)                     O(n)
  
• 空间复杂度：                                        O                            (                            1                            )                                  O(1)                     O(1)，字符一定在ASCⅡ范围内，因此哈希表大小为常数，同时记录字符的队列也是常数
  

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。