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

image.png

使用 hash 表存储字符出现次数

执行用时：31 ms, 在所有 Java 提交中击败了32.74%的用户 内存消耗：38.8 MB, 在所有 Java 提交中击败了40.80%的用户

public class Solution {

    public char firstUniqChar(String s) {
        // 存放字符出现的次数
        HashMap<Character, Integer> map = new HashMap<>();

        // 遍历字符串，实例化 map
        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 ' ';
    }
}

使用 hash 表存储字符出现次数优化版

因为题目说明了字符串只包含小写字母，所以可以使用长度为26的数组存储字符出现次数

执行用时：5 ms, 在所有 Java 提交中击败了92.45%的用户 内存消耗：38.7 MB, 在所有 Java 提交中击败了68.66%的用户

class Solution {

    public char firstUniqChar(String s) {

        int[] buckets = new int[26];
        char[] charArr = s.toCharArray();

        for (int i = 0; i < charArr.length; i++) {
            buckets[charArr[i] - 'a'] ++;
        }

        for (int i = 0; i < charArr.length; i++) {
            if (buckets[charArr[i] - 'a'] == 1) {
                return charArr[i];
            }
        }
        return ' ';
    }
}