题目的主要信息：

• 找出字符串中第一个只出现一次的字符
• 输入的字符串长度

方法一：哈希表统计频率

具体做法：

我们可以建立一个无序哈希表，遍历字符串的同时，统计每个字符出现的频率，然后再从头遍历一次字符串，在哈希表中查看每个字符串的频率，找到第一个只出现一次的字符串，返回位置，如果没找到返回-1即可。

这样我们根据返回的位置信息就可以输出相应字符。

#include<iostream>
#include<string>
#include<unordered_map>
using namespace std;

int firstNotRepeat(string& str) {
    unordered_map<char, int> mp;
    for(int i = 0; i < str.length(); i++) //统计每个字符出现的次数
        mp[str[i]]++;
    for(int i = 0; i < str.length(); i++) //找到第一个只出现一次的字母
        if(mp[str[i]] == 1)
           return i;
    return -1; //没有找到
}

int main(){
    string s;
    while(getline(cin, s)){ 
        int pos = firstNotRepeat(s); //找到该该字符的位置
        if(pos == -1) //没找到输出-1
            cout << -1 << endl;
        else
            cout << s[pos] << endl; //输出字符
    }
    return 0;
}

复杂度分析：

• 时间复杂度：$O(n)O(n)$，其中$nn$为字符串长度，两次单独的遍历
• 空间复杂度：$O(n)O(n)$，哈希表的大小最多不超过字符串长度

方法二：队列+哈希表统计位置

具体做法：

我们还可以只遍历一次，利用队列找到第一个位置。首先我们还是利用了无序哈希表，但是这次我们不是统计频率，而是统计每个字符出现位置。遍历字符串，如果遇到哈希表中没有的字符，我们入哈希表，同将字符和位置组成pair入队，然后后续如果遇到了哈希表中出现的字符，那么这个字符势必不可能是我们要找的只出现一次的字符，在哈希表中将其位置置为-1，然后弹出队列中在前面的哈希表中位置为-1的字符。因为队列是先进先出，因此队列头记录的字符一定是第一次只出现一次的字符。空队列则代表没有找到。

#include<iostream>
#include<string>
#include<unordered_map>
#include<queue>
using namespace std;

int firstNotRepeat(string& str) {
    unordered_map<char, int> mp; //统计字符出现的位置
    queue<pair<char, int> > q;
    for(int i = 0; i < str.length(); i++){
        if(!mp.count(str[i])){ //没有出现过的字符
            mp[str[i]] = i;
            q.push(make_pair(str[i], i));
        }else{ //找到重复的字符
            mp[str[i]] = -1; //位置置为-1
            while(!q.empty() && mp[q.front().first] == -1) //弹出前面所有的重复过的字符
                q.pop();
        }
    }
    return q.empty() ? -1 : q.front().second;
 }

int main(){
    string s;
    while(getline(cin, s)){ 
        int pos = firstNotRepeat(s); //找到该该字符的位置
        if(pos == -1) //没找到输出-1
            cout << -1 << endl;
        else
            cout << s[pos] << endl; //输出字符
    }
    return 0;
}

复杂度分析：

• 时间复杂度：$O(n)O(n)$，其中$nn$为字符串长度，对字符串进行一次遍历，内循环整个过程中才最多弹出$nn$次
• 空间复杂度：$O(n)O(n)$，哈希表和队列的大小最多不超过字符串长度