题目(第一次只出现一次的字符)

在字符串中找出第一个只出现一次的字符。如输入 “abaccdeff”，则输出 ‘b’。

题目一算法思路

利用 C++ 中自带的哈希表实现的数据结构 map 记录每个字符出现的次数，然后遍历此哈希表，得到第一个出现次数为 1 的字符即可。
另外，由于本题返回的类型是 char ，那么它有一个字节，8bit，即有256种可能，每个字母根据其 ASCII 码值作为数组的下标对应数组的一个数字，而数组中存储的是每个字符出现的次数。这样就创建了一个大小为256，简单且具有哈希特性的数组。

注：当所要哈希的字符有种数限制，如本题的256种，或者字母 a-z，则可以利用简单的数组来实现哈希特性。

题目二(字符流中第一次只出现一次的字符)
请实现一个函数用来找出字符流中第一个只出现一次的字符。例如，当从字符流中只读出前两个字符 “go” 时，第一个只出现一次的字符是 “g”。当从该字符流中读出前六个字符 “google” 时，第一个只出现一次的字符是 “l”。
输出描述：如果当前字符流没有存在出现一次的字符，返回 # 字符。

题目二算法思路
本题，最简单的做法就是利用题目一的完整思路，但是需要不断更新字符串，做法较不友好，但是思想简单。
而本题的做法仍然利用大小为 256 的哈希数组来存储数据。但本题不再存储字符出现的次数，而是有设定的存储某些值。
首先未出现的字符都存入值 0，即数组中默认的初始值了；如果多次出现的字符统一存入负数，如-1；如果字符首次出现那么就存入其在字符串中的次序(从 1 开始计)。那么最后为了找出字符串中第一次只出现一次的字符，我们只需遍历哈希数组，找到哈希数组中值大于 0中最小的那个所对应的字符即可。

算法实现一

算法实现二

复杂度
题目一：算法仅遍历一次字符串，因此时间复杂度为 O(n)；定义了有限长度的容器，空间复杂度可算做 O(1)。
题目二：复杂度同上。

参考
[1] <<剑指offer2>>
[2] 牛客网