JAVA练习77-第一个只出现一次的字符

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

示例 1:
输入:s = "abaccdeff"
输出:'b'

示例 2:
输入:s = "" 
输出:' '

限制:

  • 0 <= s 的长度 <= 50000

分析:

方法1:哈希表

将每个字母出现的次数存入哈希表,然后在遍历哈希表找只出现一次的字母即可。

时间复杂度:O(n) 
空间复杂度:O(C)        C <= 26

class Solution {
    public char firstUniqChar(String s) {
        //定义哈希集合存储字符和出现数次
        HashMap<Character, Integer> map = new HashMap<>();
        //遍历字符串记录次数
        for(char c: s.toCharArray()){
            map.put(c, map.getOrDefault(c, 0) + 1);
        }
        //寻找只出现一次的字符
        for(char c: s.toCharArray()){
            if(map.get(c) == 1){
                return c;
            }
        }
        return ' ';
    }
}

方法2:数组

因为 s 只包含小写字母,因此 s 最多有 26 个字母,所以我们可以创建整形数组来存储对应字母出现的次数。

时间复杂度:O(n) 
空间复杂度:O(C)        C <= 26

class Solution {
    public char firstUniqChar(String s) {
        //定义数组存储字符和出现数次
        int[] nums = new int[26];
        //遍历字符串记录次数
        for(char c: s.toCharArray()){
            nums[c-'a']++;
        }
        //寻找只出现一次的字符
        for(char c: s.toCharArray()){
            if(nums[c-'a'] == 1){
                return c;
            }
        }
        return ' ';
    }
}

题目来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/di-yi-ge-zhi-chu-xian-yi-ci-de-zi-fu-lcof

上一篇:13.4练习题5


下一篇:蓝桥杯刷题-一串单词中的字符统计