第一个只出现一次的字符

题目的主要信息：

• 在给定字符串中找到第一个只出现一次的字符的位置，位置从0开始
• 如果找不到则返回-1
• 字符串只由大小字母组成

举一反三：

学习完本题的思路你可以解决如下题目：

JZ56. 数组中只出现一次的两个数字

JZ39. 数组中出现次数超过一半的数字

JZ75. 字符流中第一个不重复的字符

方法一：哈希表统计频率（推荐使用）

知识点：哈希表

哈希表是一种根据关键码（key）直接访问值（value）的一种数据结构。而这种直接访问意味着只要知道key就能在$O(1)O(1)$时间内得到value，因此哈希表常用来统计频率、快速检验某个元素是否出现过等。

思路：

既然要找第一个只出现一次的字符，那只要我们统计每个字符在字符串中出现的次数，后续不就可以找到第一个只出现一次的字符了吗？

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

具体做法：

• step 1：遍历一次字符串，对于每个字符，放入哈希表中统计出现次数。
• step 2：再次遍历字符串，对于每个字符，检查哈希表中出现次数是否为1，找到第一个即可。
• step 3：遍历结束都没找到，那就是没有，返回-1.

具体做法：

Java实现代码：

import java.util.*;
public class Solution {
    public int FirstNotRepeatingChar(String str) {
        HashMap<Character, Integer> mp = new HashMap<>();
        //统计每个字符出现的次数
        for(int i = 0; i < str.length(); i++) 
            mp.put(str.charAt(i), mp.getOrDefault(str.charAt(i), 0) + 1);
        //找到第一个只出现一次的字母
        for(int i = 0; i < str.length(); i++) 
            if(mp.get(str.charAt(i)) == 1)
                return i;
        //没有找到
        return -1; 
    }
}

C++实现代码：

class Solution {
public:
    int FirstNotRepeatingChar(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; 
    } 
};

Python实现代码：

class Solution:
    def FirstNotRepeatingChar(self , str: str) -> int:
        mp = dict()
        #统计每个字符出现的次数
        for i in str:
            if i in mp:
                mp[i] += 1
            else:
                mp[i] = 1
        #找到第一个只出现一次的字母
        for i in range(len(str)):
            if mp[str[i]] == 1:
                return i
        #没有找到
        return -1

复杂度分析：

• 时间复杂度：$O(n)O(n)$，其中$nn$为字符串长度，两次单独的遍历
• 空间复杂度：$O(1)O(1)$，哈希表的大小最多不会超过字符集，即52个字符，属于常数空间

方法二：队列+哈希表统计位置（扩展思路）

知识点：队列

队列是一种仅支持在表尾进行插入操作、在表头进行删除操作的线性表，插入端称为队尾，删除端称为队首，因整体类似排队的队伍而得名。它满足先进先出的性质，元素入队即将新元素加在队列的尾，元素出队即将队首元素取出，它后一个作为新的队首。

思路：

上述方法一遍历了两次，有些繁琐，我们能不能在统计频率的过程中就找到第一个只出现一次的字符呢？利用先进先出的队列找到第一个位置！

首先我们还是利用了哈希表，但是这次我们不是统计频率，而是统计每个字符出现位置。遍历字符串，如果遇到哈希表中没有的字符，我们入哈希表，同将字符和位置同时各自入队，后续如果遇到了哈希表中出现的字符，那么这个字符势必不可能是我们要找的只出现一次的字符，在哈希表中将其位置置为-1：

//位置置为-1
mp[str[i]] = -1;

然后弹出队列中在前面的哈希表中位置为-1的字符。因为队列是先进先出，因此队列头记录的字符一定是第一次只出现一次的字符。

while(!q.empty() && mp[q.front().first] == -1) 
    q.pop();

空队列则代表没有找到。

具体做法：

• step 1：利用哈希表记录字符串中出现过的字符的位置，利用两个队列分别记录字符与下标位置（C++可以用pair）。
• step 2：遍历字符串，如果是没有遇到过的字符，就加入哈希表记录位置，同时字符与下标分别入队。
• step 3：遇到出现过的字符，就将其哈希表中的下标置为-1，然后弹出队列首部所有重复的字符，即位置为-1的字符。
• step 4：最后队列中剩余的队首就是第一个只出现一次的字符，因为其他的重复字符都被弹出了，队列为空就代表没有不重复的字符。

图示：

Java实现代码：

import java.util.*;
public class Solution {
    public int FirstNotRepeatingChar(String str) {
        //统计字符出现的位置
        HashMap<Character, Integer> mp = new HashMap<>();
        Queue<Character> q1 = new LinkedList<>();
        Queue<Integer> q2 = new LinkedList<>();
        for(int i = 0; i < str.length(); i++){
            //没有出现过的字符
            if(!mp.containsKey(str.charAt(i))){ 
                mp.put(str.charAt(i), i);
                q1.offer(str.charAt(i));
                q2.offer(i);
            //找到重复的字符
            }else{ 
                //位置置为-1
                mp.put(str.charAt(i), -1);
                //弹出前面所有的重复过的字符
                while(!q1.isEmpty() && mp.get(q1.peek()) == -1){
                    q1.poll();
                    q2.poll();
                }
            }
        }
        return q2.isEmpty() ? -1 : q2.poll();    
    }
}

C++实现代码：

class Solution {
public:
    int FirstNotRepeatingChar(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{ 
                //位置置为-1
                mp[str[i]] = -1; 
                //弹出前面所有的重复过的字符
                while(!q.empty() && mp[q.front().first] == -1) 
                    q.pop();
            }
        }
        return q.empty() ? -1 : q.front().second;
    } 
};

Python实现代码：

class Solution:
    def FirstNotRepeatingChar(self , str: str) -> int:
        #统计字符出现的位置
        mp = dict()
        q1 = []
        q2 = []
        for i in range(len(str)):
            #没有出现过的字符
            if str[i] not in mp:
                mp[str[i]] = i 
                q1.append(str[i])
                q2.append(i)
            #找到重复的字符
            else: 
                #重复标记位置置为-1
                mp[str[i]] = -1 
                #弹出前面所有的重复过的字符
                while len(q1) != 0 and mp[q1[0]] == -1:
                    q1.pop(0)
                    q2.pop(0)
        return -1 if len(q2) == 0 else q2[0]

复杂度分析：

• 时间复杂度：$O(n)O(n)$，对字符串进行一次遍历，内循环整个过程中才最多弹出52次
• 空间复杂度：$O(1)O(1)$，哈希表和队列的大小最多不会超过字符集，即52个字符，属于常数空间