题目描述
- 字符流中第一个只出现一次的字符
样例
输入:"google"
输出:"ggg#ll"
解释:每当字符流读入一个字符,就进行一次判断并输出当前的第一个只出现一次的字符。
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(双指针做法) $O(n)$
blablabla
时间复杂度
参考文献
C++ 代码
/*
使用hash map 来记录每个字符出现次数
可以采用双指针做法i,j往前移动,当j指向的数字出现次数大于1, i就往后移动。
实际可用队列来实现,i移动就相当于队头pop().
最后队头答案
*/
class Solution{
public:
unordered_map<char, int> cnt;
queue<int> q;
//Insert one char from stringstream
void insert(char ch){
if(++cnt[ch] > 1){
while(q.size() && cnt[q.front()] > 1) q.pop();
}else
q.push(ch);
}
//return the first appearence once char in current stringstream
char firstAppearingOnce(){
if (q.empty()) return '#';
else return q.front();
}
};