题意分析

  • 这个题目需要我们找出一个字符串里面的一个字符。这个字符需要满足以下条件。
    • 这个字符在这个字符串里面只出现了一次
    • 这个字符的位置在最前面
  • 题目需要我们返回这个字符串出现的位置（位置从0开始）

思路分析

  • 这个题目，我主要用了两种方法进行求解。

解法一 字符哈希

  • 我们首先遍历一遍整个字符串，然后用map记录下每个字符出现的次数。然后在从头遍历一遍字符串，然后返回第一个字符个数为1的字符的位置。
  • 由于只需要for循环遍历两边字符串，同时只需要存储字符串。时间复杂度为O(n)，空间复杂度为O(n) 
class Solution {
public:
    map<char,int> mp;
    int FirstNotRepeatingChar(string str) {
        int len=str.size();
        // 遍历一遍字符串，然后利用map记录每个字符出现的次数
        for(int i=0;i<len;i++){
            mp[str[i]]++;
        }
        // 再进行一次遍历字符串，返回第一个满足题目意思的字符的位置
        for(int i=0;i<len;i++){
            if(mp[str[i]]==1){
                return i;
            }
        }
        // 没有就返回-1
        return -1;
    }
};

解法二 queue+map

  • 我们可以使用queue+map进行优化，这样可以不必遍历两遍字符串。我们用一个队列queue用来存储整个字符串里面出现过的所有的字符，按照位置的先后依次入队，在入队的同时我们用一个map存储每个字符第一次出现的位置。然后我们在用一个map存储这个字符是否重复出现，这个可以根据目前的存储这个字符第一次出现的位置来进行判断。处理完之后，我们需要对队列中的元素进行出队处理，根据用来存储字符是否重复出现的那个map来进行判断。

图片说明

  • 只需要对字符串进行遍历，时间复杂度为O(n)，空间复杂度为O(n) 
class Solution {
public:
    int FirstNotRepeatingChar(string str) {
        int len=str.size();
        map<char,int> mp;  // 用来存储这个数字第一次出现的位置
        map<char,bool> count;  // 用来存储这个字符是否只出现了一次
        queue<char> q;  // 用来存储按照顺序出现的字符
        for(int i=0;i<len;i++){
            // 这个字符第一次出现
            if(mp[str[i]]==0){
                // 放到队列同时记录下他的位置
                q.push(str[i]);
                // 这里要注意的是mp默认初始化为0,所以我们不能让mp键对应的值为0
                mp[str[i]]=i+1;
            }else{
                // 这个字符出现的次数不为1
                count[str[i]]=true;
            }
        }
        // 取出队列中存储的字符，这些字符肯定是不一样的
        while(!q.empty()){
            char ch=q.front();
            // 如果这个字符没有出现重复出现
            if(count[ch]==false){
                return mp[ch]-1;
            }
            q.pop();
        }
        return -1;
    }
};