题解 | #字符流中第一个不重复的字符#

字符流中第一个不重复的字符

http://www.nowcoder.com/practice/00de97733b8e4f97a3fb5c680ee10720

描述

题目描述

这个题乍一看很复杂，其实逐步分解就可以

首先Insert这个函数是用于每次新增一个字符的，然后FirstAppearingOnce这个函数是直接输出每次第一个只出现一次的字符是什么的

样例解释

首先给定我们的样例输入

"google"

这个是怎么判断呢？

20220120223628

20220120223643

20220120223700

20220120223738

20220120223810

20220120223824

所以最后的输出就是

"ggg#ll"

题解

解法一：队列

实现思路：

首先我们可以用一个队列模拟我们每次入队的字符，然后同时我们每次记录我们这个字符出现的次数，然后查找的时候就是看我们队头是不是只出现了一次，如果是的话，我们可以直接输出，否则弹出看下一个，然后如果都不是的话就是输出 $#$

代码实现：

class Solution
{
    queue<char> q;
    int cnt[257];
//     q保存着我们的一个我们输入的字符
//     cnt里面存储的是我们每一个字符出现的位置
public:
    void Insert(char ch) {
         q.push(ch);
         ++ cnt[ch + '0'];
//         每次把我们插入的字符入队
//         并且记录出现的次数
    }
    char FirstAppearingOnce() {
        while (q.size()) {
//             如果队列不空
            char res = q.front();
//             获取队头元素
            if (cnt[res + '0'] == 1) return res;
//             如果队头是只出现了一次的，我们直接返回
            q.pop();
//             如果不是的话，直接弹出
        }
        return '#';
//         最后发现一个都没有，返回#
    }

};

时空复杂度分析：

时间复杂度： $O (n)$

理由如下：最坏清空下，我们是要遍历一半我们的这个字符流的长度

空间复杂度： $O (n)$

理由如下：我们开辟了一个记录次数的数组，然后我们的队列极限清空下会存储所有的字符流

解法二：

解题思路

首先我们可以定义一个哈希表，我们用于存储我们每一个字符出现的次数，然后我们还有一个字符串就是我们总共输入的这个字符串，我们每次插入之后可以遍历一次我们的字符串，如果我们是可以从前到后找到当前的字符满足只出现了一次的话，我们就可以把这个输出，如果都没有的话，我们最后返回的就是 $#$

代码实现

class Solution
{
    unordered_map<char, int> mp;
//     存储每一个字符出现的次数
    string s = "";
//     我们的字符串
public:
    void Insert(char ch) {
        s += ch;
//         插入我们新的字符串
        mp[ch] += 1;
//         字符的个数加一
    }
    char FirstAppearingOnce() {
        for (auto &it : s) {
            if (mp[it] == 1) return it;
        }
//         从头到尾遍历我们的字符串，如果存在一个等于1的那么我们可以直接返回
        return '#';
//         都没有的话，我们返回#
    }

};