63. 字符串中第一个只出现一次的字符
题目描述
在字符串中找出第一个只出现一次的字符。
如输入”abaccdeff”,则输出b。
如果字符串中不存在只出现一次的字符,返回 # 字符。
数据范围
输入字符串长度 [0,1000]。
样例
输入:"abaccdeff"
输出:'b'
算法1 模拟+哈希表
算法流程
首先遍历建立词频表
然后遍历,直到找到第一个出现一次的字符
时间复杂度
$O(n)$
C++ 代码
class Solution {
public:
char firstNotRepeatingChar(string s) {
unordered_map<char, int> count;
for(auto c : s) count[c]++;
for(auto c : s)
if(count[c] == 1) return c;
return '#';
}
};
错误代码: unordered_map不会维持插入时的次序
class Solution {
public:
char firstNotRepeatingChar(string s) {
unordered_map<char, int> count;
for(auto c : s) count[c]++;
for(auto p : count)
{
if(p.second == 1) return p.first;
}
return '#';
}
};