题解 | 找出字符串中第一个只出现一次的字符

#include <iostream>
#include <vector>
using namespace std;

int main() {
    string s;
    cin >> s;
    vector<int> order;          // 记录出现顺序
    vector<int> counts(26, 0);  // 记录出现次数，哈希表
    for (char& c: s) {
        counts[c - 'a']++;      // 计数
        // 判断是否为新出现的字母，是则将其下标存入 order
        if (counts[c - 'a'] == 1) {
            order.push_back(c - 'a');
        }
    }
    // 按order保存的下标顺序遍历counts
    for (auto& i: order) {
        // 如果第一次找到counts[i]是1，说明这个下标对应的字母就是结果
        if (counts[i] == 1) {
            cout << (char)(i + 'a') << endl;
            return 0;
        }
    }
    
    // 没有计数为 1 的字母
    cout << -1 << endl;
    return 0;
}

使用知识点：指针，ASCII码值，哈希表。

时间复杂度：O(n)。两次遍历，第二次遍历为常数级遍历。

空间复杂度：O(n)。一个string，两个额外数组，其中一个是固定26 int 大小的哈希表，另一个是记录哈希表下标的指针数组，大小小于等于26 int。