字符流中第一个不重复的字符
字符流中第一个不重复的字符
http://www.nowcoder.com/questionTerminal/00de97733b8e4f97a3fb5c680ee10720
描述
这是一篇针对初学者的题解。告诉你遇到新问题,该如何分析。
知识点:哈希,队列
难度:一星
题解
题目描述:对于动态字符流,返回第一个不重复的字符。如果不存在,返回'#'。
方法:哈希+队列
针对题目的描述,我们先提出两个问题?
Q1. 给定一个字符串(只不过这里的字符串是可变的),如果快速判断一个字符是否存在于字符串中,如果存在,也就是重复?
Q2. 这里先不考虑重复,如果快速返回第一个字符?有没有感觉有点像先来先服务?
对于一道题,如果没有思路,就要针对题目给自己问问题。然后针对问题,来考虑需要什么样的算法或者数据结构。
A1:对于“重复问题”,惯性思维应该想到哈希或者set。对于“字符串问题”,大多会用到哈希。因此一结合,应该可以想到,判断一个字符是否重复,可以选择用哈希,在c++中,可以选择用unordered_map<char, int>
A2:对于字符流,源源不断的往池子中添加字符,然后还要返回第一个满足什么条件的字符,显然设计到了“顺序”,也就是先来的先服务,这种先进先出的数据结构不就是队列嘛。因此,这里可以用队列。
假如你已经知道了要用hash 和 queue 这两个数据结构,你可以试着自己想一想,接下来的算法过程是怎么样的?
这里我提供一个算法过程,如下:
初始化一个
unordered_map<char, int> mp, queue<char> q
对于
Insert(char ch)
操作, 如果ch是第一次出现,则添加到q中,然后在mp中记录一下次数,如果不是第一次出现,也就是重复了,那么我们就没必要添加到q中,但是还是需要在mp中更新一下次数,因为之后要根据次数来判断是否重复。对于
FirstAppearingOnce()
操作,我们直接判断q的头部,然后在mp中检查一下,是否重复,如果没有重复,那就是我们想要的数据。否则,如果重复了,那就应该弹出头部,然后判断下一个头部是否满足要求。
根据算法的过程,你可以试着自己写一下代码。
我的示例代码如下,仅供参考:
class Solution { public: //Insert one char from stringstream queue<char> q; unordered_map<char, int> mp; void Insert(char ch) { // 如果是第一次出现, 则添加到队列中 if (mp.find(ch) == mp.end()) { q.push(ch); } // 不管是不是第一次出现,都进行计数 ++mp[ch]; } //return the first appearence once char in current stringstream char FirstAppearingOnce() { while (!q.empty()) { char ch = q.front(); // 拿出头部,如果是第一次出现,则返回 if (mp[ch] == 1) { return ch; } // 不是第一次出现,则弹出,然后继续判断下一个头部 else { q.pop(); } } return '#'; } };
时间复杂度:对于Insert(char ch)
操作,为O(1), 对于FirstAppearingOnce()
操作,为O(N),因为最坏情况下,队列中存入一半的重复数据, 比如“abcdabcd”,队列会存入“abcd”,并且弹出的时候都是重复的。
空间复杂度:O(N)