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

题目

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

示例:

s = "abaccdeff"
返回 "b"

s = "" 
返回 " "

分析

简单观察只需要 count 字符就好了，前提是保证有序。

第一次

暴力解决，遍历 count 字符，最后进行比较。注意选择有序容器。

class Solution {
    public char firstUniqChar(String s) {
        char result = ' ';
        if (s == null || s.isEmpty()) return result;
        char[] chars = s.toCharArray();
        Map<Character, Integer> map = new LinkedHashMap<>();
        for (int i = 0; i < chars.length; i++) {
            int count = map.getOrDefault(chars[i], 0);
            map.put(chars[i], ++count);
        }

        for(Map.Entry<Character, Integer> item : map.entrySet()) {
            if (item.getValue() == 1) {
                return (char) item.getKey();
            }
        }

        return result;
    }
}

第二次

不选择有序容器，遍历两次

class Solution {
    public char firstUniqChar(String s) {
        char result = ' ';
        if (s == null || s.isEmpty()) return result;
        char[] chars = s.toCharArray();
        Map<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < chars.length; i++) {
            int count = map.getOrDefault(chars[i], 0);
            map.put(chars[i], ++count);
        }

        for (char c : chars) {
            if (map.get(c) == 1) return c;
        }

        return result;
    }
}

第三次

题目限定仅有字母从 a-z 那么可以创建一个数组保存 count，再进行二次遍历保证有序。

class Solution {
    public char firstUniqChar(String s) {
        char result = ' ';
        if (s == null || s.isEmpty()) return result;
        char[] chars = s.toCharArray();
        int[] counts = new int[26];
        for (int i = 0; i < chars.length; i++) {
            counts[chars[i] - 'a']++;
        }

        for (char c : chars) {
            if (counts[c - 'a'] == 1) return c;
        }

        return result;
    }
}