剑指 Offer 50 第一个只出现一次的字符

Tag: 剑指-Offer Posted on 2022-02-27 10:33:23 Edited on 2022-02-27 10:34:01 Views: 293

概述

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 ' ';
    }
};

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