第一个只出现一次的字符
第一个只出现一次的字符
http://www.nowcoder.com/questionTerminal/1c82e8cf713b4bbeb2a5b31cf5b0417c
题目的主要信息：
- 在给定字符串中找到第一个只出现一次的字符的位置，位置从0开始
- 如果找不到则返回-1
- 字符串只由大小字母组成
举一反三：
学习完本题的思路你可以解决如下题目：
方法一：哈希表统计频率（推荐使用）
知识点：哈希表
哈希表是一种根据关键码（key）直接访问值（value）的一种数据结构。而这种直接访问意味着只要知道key就能在时间内得到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
复杂度分析：
- 时间复杂度：，其中为字符串长度，两次单独的遍历
- 空间复杂度：，哈希表的大小最多不会超过字符集，即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]
复杂度分析：
- 时间复杂度：，对字符串进行一次遍历，内循环整个过程中才最多弹出52次
- 空间复杂度：，哈希表和队列的大小最多不会超过字符集，即52个字符，属于常数空间
百威成长空间 51人发布
