题目描述

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

难度简单86收藏分享切换为英文接收动态反馈

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

示例:

s = "abaccdeff"
返回 "b"

s = "" 
返回 " "

限制：

0 <= s 的长度 <= 50000

测试用例

• 功能测试（字符串中存在只出现一次的字符；字符串中不存在只出现一次的字符；字符串中所有字符都只出现一次）
• 特殊输出测试（字符串为空指针）

题目考点

• 考察应聘者对数组和字符串的编程能力。
• 考察应聘者对哈希表的理解及运用。
• 考察应聘者对时间效率和空间效率的分析能力。

解题思路

利用哈希表，它可以是语言自带的API也可以是自己构建的Hash表，我们定义哈希表的键值是字符，而值为该字符出现的次数。

第一次扫描，每扫到一个字符，就在哈希表的对应项中把次数+1；

第二次扫描，每扫描到一个字符，就能从哈希表中得到该字符的出现次数。这样，第一个只出现一次的字符就是符合要求的输出。

参考解题

class Solution {
    public char firstUniqChar(String s) {
        Map<Character, Boolean> dic = new LinkedHashMap<>();
        char[] sc = s.toCharArray();
        for(char c : sc)
            dic.put(c, !dic.containsKey(c));
        for(Map.Entry<Character, Boolean> d : dic.entrySet()){
           if(d.getValue()) return d.getKey();
        }
        return ' ';
    }
}

补充

如果需要判断多个字符是不是在某个字符串里出现过或者统计多个字符在某个字符串出现的次数，那么我们可以考虑基于数组创建一个简单的哈希表，这样可以用很小的空间消耗换来时间效率的提升。