LeetCode 剑指 Offer 50. 第一个只出现一次的字符 题解，简单题也有细节需要注意。

题目

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

https://leetcode.cn/problems/di-yi-ge-zhi-chu-xian-yi-ci-de-zi-fu-lcof/

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

LinkedHashMap 有序map

思路

LinkedHashMap按照key插入顺序有序。因此，可以将字符逐个插入有序map，之后查看第一个个数为1的字符。

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

/*
* 执行用时：
* 24 ms
* , 在所有 Java 提交中击败了
* 42.46%
* 的用户
* 内存消耗：
* 41.7 MB
* , 在所有 Java 提交中击败了
* 61.37%
* 的用户
* 通过测试用例：
* 105 / 105
*/
public char firstUniqChar(String s) {
    if (s == null || s.length() == 0) {
        return ' ';
    }
    Map<Character, Integer> char2Cnt = new LinkedHashMap<>();
    for (char c : s.toCharArray()) {
        char2Cnt.put(c, char2Cnt.getOrDefault(c, 0) + 1);
    }
    for (Map.Entry<Character, Integer> entry : char2Cnt.entrySet()) {
        Character c = entry.getKey();
        Integer cnt = entry.getValue();
        if (cnt == 1) {
            return c;
        }
    }
    return ' ';
}

复杂度分析

时间

遍历两次字符数组长度，时间复杂度O(n)。

空间

额外使用了LinkedHashMap存储字符-》对应个数，占用n的空间。

空间复杂度O(n)。

HashMap

思路

观察发现，上述例子中，使用LinkedHashMap实际上的内存开销相对HashMap会大一些，因为有链表、节点的开销。

同时，字符数组本身就有序，我们可以只使用HashMap来完成同样的存储。

同时，存储个数使用Integer也只是用来判断是否等于1，使用Boolean则更省空间，也能完成布尔值的判断。

代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

public char firstUniqChar(String s) {
    if (s == null || s.length() == 0) {
        return ' ';
    }
    char[] arr=s.toCharArray();
    Map<Character,Boolean> char2Once=new HashMap<>();
    for(char c : arr){
        // 可简写为： char2Once.put(c,!char2Once.containsKey(c));
        if(char2Once.containsKey(c)){
            char2Once.put(c,false);
        }else{
            char2Once.put(c,true);
        }
    }
    for(char c : arr){
        if(char2Once.get(c)){
            return c;
        }
    }
    return ' ';
}

复杂度分析

同LinkedHashMap解。