剑指 Offer 50. 第一个只出现一次的字符
https://leetcode.cn/problems/di-yi-ge-zhi-chu-xian-yi-ci-de-zi-fu-lcof/
- 遍历两次数组
- 第一次遍历，通过哈希表记录每个字母出现的次数
- 第二次遍历，找到第一个只出现一次的字母
char firstUniqChar(string s) {
// base case
if (s.empty())
{
return ' ';
}
unordered_map<int, int> m; // 用哈希表来记录每个字母出现的次数
// 先遍历一次，找到每个字母出现的次数
for (const char c : s)
{
++m[c];
}
// 再遍历一次，找到第一个只出现一次的字符
for (const char c : s)
{
if (m[c] == 1)
{
return c;
}
}
return ' ';
}改进：
因为字符串只含有小写字母，可以通过一个大小为26的数组代替一般的哈希表，提高效率、空间利用率
char firstUniqChar(string s) {
// base case
if (s.empty())
{
return ' ';
}
vector<int> m(26); // 用哈希表来记录每个字母出现的次数
// 先遍历一次，找到每个字母出现的次数
for (const char c : s)
{
++m[c - 'a'];
}
// 再遍历一次，找到第一个只出现一次的字符
for (const char c : s)
{
if (m[c - 'a'] == 1)
{
return c;
}
}
return ' ';
}