剑指 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

未经允许，禁止转载，本文源站链接：https://iamazing.cn/