剑指offer_面试题55_字符流中第一个不重复的字符 *

ゝ一世哀愁。 2022-08-03 12:54 129阅读 0赞

**题目：请实现一个函数用来找出字符流中第一个只出现一次的字符。**

例如，当从字符流中只读出前两个字符“go”时，第一个只出现一次的字符是“g”。当从该字符流中读出前六个字符“google”时，第一个只出现一次的字符时“l”。

**ps. 本题，我在阿里二面的时候，被问到了，需要注意。**

**第一种解法：**

一种很笨的解法，时间效率低下，但确是我的第一反应。需要记下以便反思。

1、首先用一个指针指向第一个出现的字符，然后用第二指针，指向出现的第二个字符，并让第二指针向后移动，当出现和第一个指针相同的字符时，将这两个字符置为 “ \* ”

2、一轮遍历后，第二个指针向后移动一位，再次用第二个指针遍历，方式和步骤一 一样，这样经过 n 轮遍历。所有重复的字符都变成了 “ \* ”

3、然后重新遍历，当出现第一个不是 “ \* ”的字符时，就找到了第一个只出现一次的字符

如上步骤所说，这种方法效率十分低下，需要更加高效的方法。

**第二种解法：**

对这个题目思考，可以发现，出现的字符 和 它的出现的次数 是一种对应关系，自然联想到 **哈希表**的 **key-value** 这种对应，或者应用 **关联容器 map**，可以很方便的解决这个问题。

map 容器中，它的一个元素 就是一组（key，value）对应的数据。建议 先去 了解一下 哈希表 和 map 的相关概念和原理。

![20150807094452977][]

以下是第二种解法的代码：

#include <iostream>
    #include <map>
    #include <string>
    #include <cstdlib>      /*exit()的头文件*/
    //#include <exception>
    
    using namespace std;
    
    char First_appearing_once(string str)
    {
        if(str.empty())
        {
            //throw new exception;
            cout << "字符串为空" << endl;
            exit(1);   /*异常退出*/
        }
    
        map<char,int> word_count;
        /**unsigned int i;这里要用无符号整型，因为size()产生的是无符号整型；直接用int，会产生警告*/
        string::size_type i;                       /**size_type 就是容器中定义的无符号整型*/
        char target_ch;
        for(i = 0; i < str.size(); i++)
        {
            ++word_count[str[i]];
        }
        for(i = 0; i < str.size(); i++)
        {
            if(1 == word_count[str[i]])
            {
                target_ch = str[i];
                break;
            }
        }
    
        return target_ch;
    }
    
    
    int main()
    {
        //string str("abbacde");
        //string str("google");
        //string str;
        string str("abbacde cdgoogle ");
        char x;
        x = First_appearing_once(str);
        cout << x << endl;
        return 0;
    }

结果如下：

![20150807095048077][]

**PS：疑问：在上述代码中，当字符串为空时，如何抛出异常，并退出程序？**

可以看到在代码中我注释掉的部分 “ throw new exception; ” 这样写有点问题，就是在程序会退出时，会出现 “例如程序崩溃时” 出现的弹框。

这个问题我没有解决，只能用 exit（1）代替了。

我在 抛出异常 这一块 不是很熟练，如果有 哪位 大神 会，麻烦解答一下，谢谢。

/\*点滴积累，我的一小步O(∩\_∩)O~\*/

[20150807094452977]: /images/20220731/bda15749214b4b53add1b3f24cc28c01.png
[20150807095048077]: /images/20220731/1f7dad4613b6409fbab34c162d4600da.png