题目描述

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

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

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

样例

输入："abaccdeff"

输出：'b'

算法

(哈希表) $O(n)$

1. 遍历一遍字符串用哈希表存储每个字符出现的次数
2. 再遍历一遍字符串遇到只出现一次的字符返回即可，否则返回 $#$

时间复杂度

字符串被遍历两次，时间复杂度为 $O(n)$

C++ 代码

class Solution {
public:
    char firstNotRepeatingChar(string s) {
        unordered_map<char, int> hash;

        for (auto x : s) hash[x] ++ ;
        for (auto x : s)
            if (hash[x] == 1)
                return x;
        return '#';
    }
};