首页 > 代码库 > 55 - 字符流中第一个不反复的字符
55 - 字符流中第一个不反复的字符
当从字符流中仅仅读出前两个字符“go”时,第一个仅仅出现一次的字符是‘g’。当从该字符流中读出前六个字符“google”时。第一个仅仅出现 1 次的字符是”l”。
首先要记录一个字符出现的次数,为了实现O(1)查找。使用简易hash表存储。用occurences[256] 记录字符出现的次数。设置:
occurences[i] = 0, 该字符未出现;
occurences[i] = 1, 该字符出现一次;
occurences[i] = 2, 该字符出现2次或大于2次
使用先进先出的队列记录。出现一次的字符。
在后面的字符输入过程中,可能会输入一个已经存在一次的字符,队列里可能存在不止出现一次的字符。因此在取队列顶元素时,应再次检查该元素是否出现1次,假设不是,则队列pop。直至找到一个仅仅出现一次的字符索引。
时间复杂度O(1)。
空间复杂度:occurences[256] 空间恒定;队列最多仅仅会存在256个字符(仅仅会push第一次出现的字符)。因此空间复杂度O(1)
#include <iostream>
#include <queue>
using namespace std;
class CharStatics {
private:
unsigned int occurences[256];
int index;
queue<int> index_queue;
public:
CharStatics() {
index = -1;
for (int i = 0; i <= 255; i++)
occurences[i] = 0;
}
void InsertChar(char ch) {
if (occurences[ch] == 0) {
occurences[ch] = 1; // 第一次出现,设置出现次数,压入队列
index_queue.push(ch);
} else {
occurences[ch] = 2;// 第 2 次或多次出现
}
}
char FirstApperingOnce() {
// 找到最先仅仅出现一次的字符,并用index指向
while (!index_queue.empty() && occurences[index_queue.front()] != 1) {
index_queue.pop();
}
if (!index_queue.empty())
index = index_queue.front();
else
index = -1; // 没有仅仅出现一次的字符
if (index == -1)
return ‘\0‘;
return index+‘\0‘;
}
};
int main() {
CharStatics str;
str.InsertChar(‘g‘);
cout << str.FirstApperingOnce() << endl;
str.InsertChar(‘o‘);
cout << str.FirstApperingOnce() << endl;
str.InsertChar(‘o‘);
cout << str.FirstApperingOnce() << endl;
str.InsertChar(‘g‘);
cout << str.FirstApperingOnce() << endl;
str.InsertChar(‘l‘);
cout << str.FirstApperingOnce() << endl;
str.InsertChar(‘e‘);
cout << str.FirstApperingOnce() << endl;
}
输出:
g
g
g
NUL
l
l
55 - 字符流中第一个不反复的字符
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。