每日一练（23）：第一个只出现一次的字符

在字符串 s 中找出第一个只出现一次的字符。如果没有，返回一个单空格。 s 只包含小写字母。

示例 1:

输入：s = "abaccdeff"

输出：'b'

示例 2:

输入：s = ""

输出：' '

限制：

0 <= s 的长度 <= 50000

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/probl...

方法一：哈希表

思路

对字符串进行两次遍历。

• 遍历字符串 s ，使用哈希表统计 “各字符数量是否 >1 ”。
• 再遍历字符串 s ，在哈希表中找到首个 “数量为 1 的字符”，并返回。

算法

1.字符统计： 遍历字符串 s 中的每个字符 c ；

• 若 dic 中 不包含 键(key) c ：则向 dic 中添加键值对 (c, True) ，代表字符 c 的数量为 1 ；
• 若 dic 中 包含 键(key) c ：则修改键 c 的键值对为 (c, False) ，代表字符 c 的数量 >1 。

2.查找数量为 1 的字符： 遍历字符串 s 中的每个字符 c ；

• 若 dic中键 c 对应的值为 True ：，则返回 c 。

3.返回 ' ' ，代表字符串无数量为 1 的字符。

char firstUniqChar(string s) {
    if (s.empty()) {     //注意边界情况的处理！特别是s为空字符串的情况
        return ' ';
    }
    unordered_map<int, bool> dic;
    for (char c : s) {
        dic[c] = dic.find(c) == dic.end();
    }
    for (char c : s) {
        if (dic[c]) {
            return c;
        }
    }
    return ' ';
}

方法二：巧用string容器的查找函数

思路和算法

• s.find(s[i]) : 返回字符串s中从左向右查找s[i]第一次出现的位置；
• s.rfind(s[i]) : 返回字符串s中从右向左查找s[i]第一次出现的位置；

此方法虽然看起来代码简洁，但是时间复杂度较高!

char firstUniqChar(string s) {
    if (s.empty()) {    //注意边界情况的处理！特别是s为空字符串的情况
        return ' ';
    }
    int n = s.size();
    for(int i = 0; i < n; i++){
        if(s.find(s[i]) == s.rfind(s[i])){
            return s[i];
        }
    }
    return ' ';
}