64. 字符流中第一个只出现一次的字符
题目描述
请实现一个函数用来找出字符流中第一个只出现一次的字符。
例如,当从字符流中只读出前两个字符 go 时,第一个只出现一次的字符是 g。
当从该字符流中读出前六个字符 google 时,第一个只出现一次的字符是 l。
如果当前字符流没有存在出现一次的字符,返回 # 字符。
样例
输入:"google"
输出:"ggg#ll"
解释:每当字符流读入一个字符,就进行一次判断并输出当前的第一个只出现一次的字符。
算法1 字符串+哈希表
算法流程
string记录加入的字符,哈希表记录字符出现的次数
查找时遍历字符串以确定第一个出现一次的字符
时间复杂度
$O(n^2)$
因为可能每次都会执行一次查找
C++ 代码
class Solution{
public:
unordered_map<char, int> count;
string s;
//Insert one char from stringstream
void insert(char ch){
s += ch;
count[ch]++;
}
//return the first appearence once char in current stringstream
char firstAppearingOnce(){
for(auto c : s)
if(count[c] == 1) return c;
return '#';
}
};
算法2 用队列实现的双指针算法
将$O(n^2)$的算法优化成$O(n)$的一般方法:双指针、单调队列
算法流程
答案一定是从前往后找的 –> 是有一定单调性的
时间复杂度 $O(n)$
指针只增不减,调用n次,总共下来共走n次
C++ 代码
class Solution{
public:
unordered_map<char, int> count;
queue<char> q;
//Insert one char from stringstream
void insert(char ch){
if(++count[ch] > 1) //保证队头一定只出现一次
while(q.size() && count[q.front()] > 1) q.pop();
else q.push(ch);
}
//return the first appearence once char in current stringstream
char firstAppearingOnce(){
if(q.empty()) return '#';
return q.front();
}
};
总结
注意字符流和字符串的处理区别