题目描述

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

示例:

s = "abaccdeff"
返回 "b"

s = "" 
返回 " "

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/di-yi-ge-zhi-chu-xian-yi-ci-de-zi-fu-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路分析

• 这个题目题意简单，难点是返回第一个只出现一次的字符。

• 首先，我们可以使用 hashMap 来存储每个字符出现的次数。然后在重新遍历字符串就可以得出答案。代码如下：

代码

    public char firstUniqChar(String s) {
        Map map = new HashMap<>();
        for (char ch : s.toCharArray()) {
            map.put(ch, map.getOrDefault(ch, 0) + 1);
        }
        Set set = new HashSet<>();
        for (Map.Entry entry : map.entrySet()) {
            if (entry.getValue() == 1) {
                set.add(entry.getKey());
            }
        }
        char ans = ' ';
        if (set.size() > 0) {
            for (char ch : s.toCharArray()) {
                if (set.contains(ch)) {
                    ans = ch;
                    break;
                }
            }
        }
        return ans;
    }

• 这个题目虽然不难，但是一不小心就容易写出冗余低效的代码。写出精简,高效的代码还是需要多练习。优化后的代码如下：

    public char firstUniqChar(String s) {
        int[] cnt = new int[256];
        char[] chars = s.toCharArray();
        for (char ch : chars) {
            cnt[ch]++;
        }
        char ans = ' ';
        for (char ch : chars) {
            if (cnt[ch] == 1) {
                ans = ch;
                break;
            }
        }

        return ans;
    }

总结

• 上述代码的时间复杂度是 O(n), 空间复杂度是O(n)

• 上述优化的代码，主要使用 ASCII 码思想优化。

• 简单介绍一下ASCII 码相关知识。在计算机中，所有的数据在存储和运算时都要使用二进制数表示（因为计算机用高电平和低电平分别表示1和0）。而 ASCII 码就是存储的通用规范。ASCII 码使用指定的 7 位或 8 位二进制数组合来表示 128 或 256 种可能的字符。标准 ASCII 码也叫基础ASCII码，使用 7 位二进制数来表示所有的大写和小写字母，数字 0 到 9、标点符号，其中 32～126(共95个)是字符(32sp是空格），其中48～57为0到9十个阿拉伯数字；65～90为26个大写英文字母，97～122号为26个小写英文字母，其余为一些标点符号、运算符号等。

• 坚持每日一题，加油！