剑指 Offer 50 第一个只出现一次的字符
概述
https://leetcode-cn.com/problems/di-yi-ge-zhi-chu-xian-yi-ci-de-zi-fu-lcof/
列表 + 哈希表
用某种有序的数据结构存储候选者,如果出现两次则将其标记(不能直接剔除,因为如果之后再遇到的话就将当成新的值了)。
本来是打算用 vector 存储 <char, count> pair 的,实际上没必要,直接用字符标记该项不可选即可。
class Solution {
public:
char firstUniqChar(string s) {
unordered_map<char, int> char2idx;
vector<char> counter;
for (auto c : s) {
if (char2idx.count(c) == 0) {
char2idx[c] = counter.size();
counter.push_back(c);
} else {
counter[char2idx[c]] = ' ';
}
}
for (auto c : counter) {
if (c != ' ') return c;
}
return ' ';
}
};
Links: sword-offer-50