剑指offer-54：字符流中第一个不重复的字符

目录

剑指offer-54字符流中第一个不重复的字符目录 1问题描述2哈希表3解析及答案

1问题描述

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

如果当前字符流没有存在出现一次的字符，返回#字符。

2哈希表

哈希表是一种高效的数据结构，能在平均时间复杂度O(n)的情况下存储与查询。它是根据关健值（key）进行访问的。存在一函数，当key传入函数之后，函数输出一个独一无二的值val，函数叫哈希函数。当给定所存储容器V大小为m时，那么输入元素所在的位置就是val % m。

当输入很多元素之后， 同一位置下就可能会存入多个元素，因而产生冲突（collision），那么这时候就需要用链接（chaining）来解决问题：使用链表将同一位置下的元素链起来。

支持的操作： 1、insert 插入元素 2、erase 删除元素 3、search 搜索元素

示意图：

3解析及答案

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

map 容器中，它的一个元素 就是一组（key，value）对应的数据

class Solution{ public: //Insert one char from stringstream string str; char hash[256]={0}; //哈希表，键值对 void Insert(char ch){ str+=ch; hash[ch]++; } //return the first appearence once char in current stringstream char FirstAppearingOnce(){ int size=str.size(); for(int i=0;i<size;++i){ if(hash[str[i]]==1) return str[i]; } return '#'; } };