题目描述
字符流中第一个只出现一次的字符
样例
输入:"google"
输出:"ggg#ll"
解释:每当字符流读入一个字符,就进行一次判断并输出当前的第一个只出现一次的字符。
算法1
(hash)
和前面那个字符串中第一个只出现一次的字符是一样的,不过这个是在数据流中。一样的代码。
时间复杂度
O(n^2)
C++ 代码
class Solution{
public:
Solution():myStr(""){};
//Insert one char from stringstream
void insert(char ch){
myStr += ch;
maps[ch]++;
}
//return the first appearence once char in current stringstream
char firstAppearingOnce(){
for(auto c:myStr)
{
if(maps[c] == 1)
return c;
}
return '#';
}
string myStr;
unordered_map<char,int> maps;
};
算法2
(hash)
这个和之前的那个字符串中第一个只出现一次的字符是有点区别的,这个hashmap里面存的是每个字符出现的下标,如果出现两次就将其设置为-1,然后寻找过程中,找到hashmap中value不等于-1的且是最小的对应的key,就是最后的答案。
时间复杂度
O(n^2)
参考文献
剑指offer
C++ 代码
class Solution{
public:
Solution():index(0){};
//Insert one char from stringstream
void insert(char ch){
if(maps.find(ch) == maps.end())
maps[ch] = index;
else
maps[ch] = -1;
index++;
}
//return the first appearence once char in current stringstream
char firstAppearingOnce(){
char ans = '#';
int minIndex = index;
for(auto i:maps)
{
if(i.second != -1 && minIndex > i.second)
{
minIndex = i.second;
ans = i.first;
}
}
return ans;
}
int index;
unordered_map<char,int> maps;
};