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

title: 每日一练（23）：第一个只出现一次的字符
categories:[剑指offer]
tags:[每日一练]
date: 2022/02/22
每日一练（23）：第一个只出现一次的字符在字符串 s 中找出第一个只出现一次的字符。如果没有，返回一个单空格。 s 只包含小写字母。
示例 1:
输入：s = "abaccdeff"
输出：'b'
示例 2:
输入：s = ""
输出：' '
【每日一练（23）（第一个只出现一次的字符）】限制：
0 <= s 的长度 <= 50000
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/probl...
方法一：哈希表
思路 1.对字符串进行两次遍历。

遍历字符串 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 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 ' '; }