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

传送门

nowcoder
leetcode

题目描述

在一个字符串中找到第一个只出现一次的字符，并返回它的位置，
如果没有则返回 -1（需要区分大小写、从 0 开始计数）。
数据范围：0 <= n <= 10000，字符串只有字母组成。
要求：时间复杂度 O(n)，空间复杂度 O(n)

C++ 代码 - nowcoder

/*
    哈希表：字符数组代替

    时间复杂度：O(n)
        n 表示字符串 str 的长度。
    空间复杂度：O(Σ)
        其中 Σ 是字符集，由于本题中 s 只包含大小写字母，因此 Σ <= 52。
*/
class Solution {
public:
    int FirstNotRepeatingChar(string str) {
        vector<int> count(58, 0);
        for (int i = 0; i < str.size(); i ++) {
            count[str[i] - 'A'] += 1;
        }
        for (int i = 0; i < str.size(); i ++) {
            if (count[str[i] - 'A'] == 1) return i;
        }
        
        return -1;
    }
};

/*
    哈希表：unordered_map

    时间复杂度：O(n)
    空间复杂度：O(Σ)
*/
class Solution {
public:
    int FirstNotRepeatingChar(string str) {
        unordered_map<char, int> ch2cnt;
        for (int i = 0; i < str.size(); i ++) {
            ch2cnt[str[i]] += 1;
        }
        for (int i = 0; i < str.size(); i ++) {
            if (ch2cnt[str[i]] == 1) return i;
        }

        return -1;
    }
};

C++ 代码 - leetcode

/*
    哈希表：字符数组代替

    时间复杂度：O(n)
    空间复杂度：O(Σ)
*/
class Solution {
public:
    char dismantlingAction(string s) {
        int count[26] = {};
        for (char c : s) {
            count[c - 'a'] ++; // 字符转化成数字
        }
        for (int i = 0; i < s.length(); i ++) {
            char c = s[i];
            if (count[c - 'a'] == 1) {
                return c; // 第一个出现一次的字符
            }
        }

        return ' ';
    }
};