【剑指offer系列】50. 字符串中第一个只出现一次的字符

在字符串中找出第一个只出现一次的字符。

如输入 "abaccdeff"，则输出b。

如果字符串中不存在只出现一次的字符，返回# 字符。

数据范围
输入字符串长度 [0,1000]。

样例：

输入："abaccdeff"

输出：'b'

方法一：
第一次遍历，统计所有字母出现的次数；
第二次遍历，找到第一个只出现一次的字母，若找不到就返回’#’；

方法2：
常规哈希表的使用，这里带大家再回顾一下哈希表数据结构，

哈希表 ：也叫做散列表。是根据关键字和值（Key-Value）直接进行访问的数据结构。也就是说，它通过关键字 key 和一个映射函数 Hash(key) 计算出对应的值 value，然后把键值对映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做哈希函数（散列函数），用于存放记录的数组叫做 哈希表（散列表）。 哈希表的关键思想是使用哈希函数，将键 key 和值 value 映射到对应表的某个区块中。可以将算法思想分为两个部分：

1. 向哈希表中插入一个关键字：哈希函数决定该关键字的对应值应该存放到表中的哪个区块，并将对应值存放到该区块中
2. 在哈希表中搜索一个关键字：使用相同的哈希函数从哈希表中查找对应的区块，并在特定的区块搜索该关键字对应的值

简易热身题，时间复杂度为 O(n)。

// 方法一：
class Solution {
public:
    char firstNotRepeatingChar(string s) {
        unordered_map res;
        for(auto x:s) res[x]++;//统计次数

        for(auto x:s)
            if(res[x]==1) return x;

        return '#';
    }
};

// 方法二：哈希表
class Solution {
public:
    char firstNotRepeatingChar(string s) {
        unordered_mapmap;
        for(auto x : s)
        {
            map[x]++;
        }
        char res = '#';
        for(auto x: s){
            if(map[x] == 1)
           { res = x;
            return res;}
        }
        return res;


    }
};