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

た入场券 2022-11-21 11:37 158阅读 0赞

# 题目 #

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

示例:

> s = “abaccdeff”  
> 返回 “b”

> s = “”  
> 返回 " "

限制：

*  0 <= s 的长度 <= 50000

来源：力扣（LeetCode）  
链接：[https://leetcode-cn.com/problems/di-yi-ge-zhi-chu-xian-yi-ci-de-zi-fu-lcof][https_leetcode-cn.com_problems_di-yi-ge-zhi-chu-xian-yi-ci-de-zi-fu-lcof]

# 解题思路 #

本题使用哈希表来解决

*  创建一个有序哈希表
 *  字符串转换成字符数组
 *  循环记录字符出现的次数，只出现一次记为true，多次记为false
 *  循环有序哈希表，如果有值为true的，直接返回key
 *  没有就返回单空格

# 代码 #

class Solution { 
        public char firstUniqChar(String s) { 
            // 特殊判断
            if (s.length() == 0) { 
                return ' ';
            }
    
            // 使用有序map记录
            LinkedHashMap<Character, Boolean> map = new LinkedHashMap<>();
            char[] cArray = s.toCharArray();
            // 迭代字符数组
            for (char c : cArray) { 
                map.put(c, !map.containsKey(c));
            }
    
            // 迭代有序map
            for (Map.Entry<Character, Boolean> entry : map.entrySet()) { 
                if (entry.getValue()) { 
                    return entry.getKey();
                }
            }
            return ' ';
        }
    }

# 复杂度 #

*  时间复杂度:O(n)，最多循环2n次
 *  空间复杂度:O(1)，s只包含小写字母，最多为O(26)，常数级别额外空间

[https_leetcode-cn.com_problems_di-yi-ge-zhi-chu-xian-yi-ci-de-zi-fu-lcof]: https://leetcode-cn.com/problems/di-yi-ge-zhi-chu-xian-yi-ci-de-zi-fu-lcof