剑指 Offer 50. 第一个只出现一次的字符

大家好，我是吴师兄。

今天继续来学习《剑指Offer》系列的一道经典题目，依旧给出了非常详细的题解和精美的配图与动画。

一、题目描述

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

示例 1:

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

示例 2:

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

二、题目解析

为了帮助你更好的理解整个过程，我特意做了一组动画，点开可以查看：

三、参考代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
class Solution {
    public char firstUniqChar(String s) {

        // 设置哈希表用来记录字符串中每个字符是否只出现过一次
        // key 为字符
        // value 为 boolean 类型
        // true 代表当前遍历的字符中，该字符出现了一次
        // false 代表当前遍历的字符中，该字符出现了两次或两次以上
        HashMap<Character, Boolean> dic = new HashMap<>();

        // 首先将字符串转换为字符数组的形式，方便遍历
        char[] charArray = s.toCharArray();

        // 遍历字符数组中的每个字符
        for(char c : charArray){
            
            // 1、首先以该字符作为 key ，在字典中进行查找是否存在
            Boolean result = dic.containsKey(c);

            // 2、如果该字符在字典中已经存在
            // 那么说明当前遍历的字符中，该字符出现了两次或两次以上
            if(result){

                // 所以将 value 更新为 false
                dic.put(c,false);

            // 3、如果该字符在字典中不存在
            // 那么说明当前遍历的字符中，该字符目前只出现了一次
            }else{

                // 将 value 更新为 true
                dic.put(c,true);
            }

        }
        
        // 再一次从头到尾遍历字符数组
        for(char c : charArray){

            // 以该字符作为 key ，在字典中进行查找对应的 value
            Boolean result = dic.get(c);

            // 如果发现 value 值为 true
            // 那么说明找到了第一个只出现一次的字符
            if(result){

                // 返回这个字符
                return c;

            }
        }

        // 否则说明所有字符都出现了两次或两次以上，或者字符串为空
        // 那么返回 ' '
        return ' ';
    }
}