50. 第一个只出现一次的字符
1. 描述
在字符串 s 中找出第一个只出现一次的字符。如果没有，返回一个单空格。 s 只包含小写字母。
2. 例子
示例 1:
s = “abaccdeff”
返回 “b”
示例 2:
s = ""
返回 " "
3. 限制
- 0 <= s 的长度 <= 50000
4. 题解
m = i_letters.size(), 是 i_letters 中出现的不同字符个数
时间复杂度: O(m)
空间复杂度: O(n)，由于整个字符集也不过 128 或 256 等，可以视为 O(1)
class Solution
{
public:
// char firstUniqChar(string s)
char firstUniqChar(string &i_letters)
{
unordered_map<char, int> lastLetterIndex;
for(int i = 0; i < i_letters.size(); i++)
{
char letter = i_letters[i];
if(lastLetterIndex.find(letter) == lastLetterIndex.end())
lastLetterIndex[letter] = i;
else
lastLetterIndex[letter] = INT_MAX;
}
char occurOnceLetter = ' ';
lastLetterIndex[occurOnceLetter] = INT_MAX;
for(auto iter : lastLetterIndex)
{
if(iter.second < lastLetterIndex[occurOnceLetter])
occurOnceLetter = iter.first;
}
return occurOnceLetter;
}
};