每日一题 - 剑指 Offer 50. 第一个只出现一次的字符

每日一题 - 剑指 Offer 50. 第一个只出现一次的字符

题目信息

时间： 2019-07-03

题目链接：Leetcode

tag：哈希表

难易程度：简单

题目描述：

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

示例:

s = "abaccdeff" 返回 "b" s = "" 返回 " "

注意

1. 0 <= s 的长度 <= 50000

解题思路

本题难点

字符串查找第一个只出现一次的字符，性能最优。

具体思路

哈希表

遍历字符串 s：使用哈希表统计 “各字符数量是否 >1 ”。再遍历字符串 s ：在哈希表中找到首个 “数量为 1的字符”，并返回。

代码

class Solution { public char firstUniqChar(String s) { HashMap<Character, Boolean> dic = new HashMap<>(); char[] sc = s.toCharArray(); for(char c : sc) dic.put(c, !dic.containsKey(c)); for(char c : sc) if(dic.get(c)) return c; return ' '; } }

复杂度分析：

时间复杂度 O(N) ：N为字符串 s的长度；需遍历 s 两轮，使用 O(N) ；HashMap 查找的操作复杂度为 O(1)；空间复杂度 O(N) ：HashMap 需存储 N 个字符的键值对，使用 O(N)大小的额外空间。

其他优秀解答

解题思路

有序哈希表，在字符串很长时， 效率更高。

代码

class Solution { public char firstUniqChar(String s) { char[] array = s.toCharArray(); HashMap<Character,Boolean> map = new LinkedHashMap<>(); // 遍历字符串 s 中的每个字符 c ； for(char c:array){ //若 dic 中 不包含 键(key) c ：则向 dic 中添加键值对 (c, True) ，代表字符 c 的数量为1 //若 dic 中 包含 键(key) c ：则修改键 c 的键值对为 (c, False) ，代表字符 c 的数量 >1 map.put(c,!map.containsKey(c)); } // 判断存在时，直接遍历entrySet，而不是遍历原字符串。在`aaaab`时，效率高 for(Map.Entry<Character,Boolean> entry:map.entrySet()){ if(entry.getValue()){ return entry.getKey(); } } return ' '; } }