【面试题】第一个只出现一次的字符（三种解法）
题目描述 
文章图片
解法一：哈希表计数法 需要从头开始扫描字符串两次。 第?次扫描字符串时， 每扫描到?个字符就在哈希表的对应项中把次数加1。 接下来第?次扫描时， 每扫描到?个字符就能从哈希表中得到该字符出现的次数。 当遇到第?个只出现?次的字符就是符合要求的结果。
java
class Solution {
public char firstUniqChar(String s) {
HashMap map = new HashMap<> ();
char[] char_array = s.toCharArray();
for(char c:char_array){
map.put(c, map.getOrDefault(c, 0)+1);
}
for(char c:char_array) {
if(map.get(c) == 1) // 一旦遇到出现次数为 1的字符，就直接返回
return c;
}
/*
Java中单引号内的数据 是char类型的，单引号只能引一个字符（表示单个字符）
双引号内的数据 是String类型的，双引号可以引0个及其以上（引用字符串）
*/
return ' ';
// 字符串无只出现一次的字符
}
}
解法二：改进哈希表的value为布尔型 Map 结构的 Value 使用 Boolean 类型是一个更好的选择，原因如下：
- 只要某一个字符出现的次数大于 1 次就不符合要求了，这个时候使用 Fasle 标记状态相对于 Integer 的不断递增来说更合理，也更省空间。
- 布尔值可以直接用来判断，简化代码逻辑。
class Solution {
public char firstUniqChar(String s) {
HashMap dic = new HashMap<> ();
char[] char_array = s.toCharArray();
// 字符串转为字符数组，便于遍历
for(char c:char_array){
/*
若 dic中不包含键(key) c ：则向 dic中添加键值对(c, True)，代表字符 c的数量为 1;
若 dic中包含键(key) c ：则修改 dic中键 c的值为 False，代表字符 c的数量 > 1;
*/
dic.put(c, !dic.containsKey(c));
}
for(char c:char_array) {
if(dic.get(c)) // 若 dic中键 c对应的值为 True，则返回 c
return c;
}
return ' ';
// 字符串无只出现一次的字符
}
}
解法三：有序哈希表 在哈希表的基础上，有序哈希表中的键值对是按照插入顺序排序的。基于此，可通过遍历有序哈希表而不是再次遍历原始字符串，实现搜索首个出现次数为 1 的字符。
【【面试题】第一个只出现一次的字符（三种解法）】由于哈希表是去重的，即哈希表 dic 中键值对数量 ≤ 字符串 s 的长度。因此，相对前面的方法，第二轮遍历次数减少了，特别是当字符串很长且重复字符很多时，采用有序哈希表效率更高。
class Solution {
public char firstUniqChar(String s) {
HashMap dic = new LinkedHashMap<> ();
// 定义有序哈希表
char[] char_array = s.toCharArray();
// 字符串转为字符数组，便于遍历
for(char c:char_array){
/*
若 dic中不包含键(key) c ：则向 dic中添加键值对(c, True)，代表字符 c的数量为 1;
若 dic中包含键(key) c ：则修改 dic中键 c的值为 False，代表字符 c的数量 > 1;
*/
dic.put(c, !dic.containsKey(c));
}
for(Map.Entry d: dic.entrySet()) {
/*
Map提供了一些常用方法：
keySet()方法返回值是Map中key值的集合；
entrySet()的返回值也是一个Set集合，此集合的类型为Map.Entry。Map.Entry是Map声明的一个内部接口，此接口为泛型，定义为Entry。
它表示Map中的一个实体（一个key-value对）。接口中有getKey(),getValue()方法。
*/
if(d.getValue())// 若遇到某个字符对应键值对的value为True，返回其key即该字符
return d.getKey();
}
return ' ';
// 字符串无只出现一次的字符
}
}
参考
https://leetcode-cn.com/problems/di-yi-ge-zhi-chu-xian-yi-ci-de-zi-fu-lcof/solution/mian-shi-ti-50-di-yi-ge-zhi-chu-xian-yi-ci-de-zi-3/
