剑指 Offer 50. 第一个只出现一次的字符 た 入场券 2022-11-21 11:37 107阅读 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
还没有评论,来说两句吧...