第一个只出现一次的字符

## 1 题目

在字符串 s 中找出第一个只出现一次的字符。如果没有，返回一个单空格。 s 只包含小写字母。

**示例 1:**

```txt
输入：s = "abaccdeff"
输出：'b'
```

**示例 2:**

```txt
输入：s = ""
输出：' '
```

**限制：**

* 0 <= s 的长度 <= 50000

## 2 解题思路

> 本题考察**哈希表**的使用，下面主要介绍**哈希表**和**有序哈希表**两种解法，其中，**在字符串长度较大**、**重复字符很多时**，**有序哈希表解法理论上效率更高**。

### 2.1 哈希表

#### 2.1.1 问题分析

1. **遍历字符串 $s$**，**使用哈希表统计 $ 各字符数量是否 \gt 1$**。
2. **再遍历字符串 $s$**，**在哈希表中找到首个 $ 数量为 1 的字符 $**，**并返回**。

![Picture1.png](/media/202202/2022-02-10_1640530.3928294457202771.png)

#### 2.1.2 参考代码

```java
/**
 * 剑指 Offer 50. 第一个只出现一次的字符（版本 1：哈希表）
 * @param s 字符串
 * @return  字符串中第一个只出现一次的字符
 */
public char firstUniqCharV1(String s) {
    HashMap<Character, Boolean> map = new HashMap<>();

for (char c: s.toCharArray()) {
        map.put(c, !map.containsKey(c));
    }

for (char c: s.toCharArray()) {
        if (map.get(c)) {return c;}
    }

return ' ';
}
```

### 2.2 有序哈希表

#### 2.2.1 问题分析

1. **在哈希表的基础上**，**有序哈希表中的键值对是按照插入顺序排序的**，**基于此**，**可通过遍历有序哈希表**，**实现搜索首个 $ 数量为 1 的字符 $**。
2. **哈希表是去重的**，**即哈希表中 $ 键值对数量 \le 字符串 s 的长度 $**，**因此**，**相比于[哈希表](#2-1-哈希表)**，**有序哈希表减少了第二轮遍历的循环次数**，**当字符串很长**（重复字符很多）**时**，**有序哈希表则效率更高**。

#### 2.2.2 参考代码

```java
/**
 * 剑指 Offer 50. 第一个只出现一次的字符（版本2：有序哈希表）
 * @param s 字符串
 * @return  字符串中第一个只出现一次的字符
 */
public char firstUniqCharV2(String s) {
    Map<Character, Boolean> map = new LinkedHashMap<>();

for (char c: s.toCharArray()) {
        map.put(c, !map.containsKey(c));
    }

for (Map.Entry<Character, Boolean> entry: map.entrySet()) {
        if (entry.getValue()) {return entry.getKey();}
    }

return ' ';
}
```

## 参考文献

1. [剑指 Offer 50. 第一个只出现一次的字符](https://leetcode-cn.com/problems/di-yi-ge-zhi-chu-xian-yi-ci-de-zi-fu-lcof)。
2. [面试题 50. 第一个只出现一次的字符（哈希表 / 有序哈希表，清晰图解）](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)。