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