第一个只出现一次的字符

题目描述

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

s = "abaccdeff"
返回 "b"

s = "" 
返回 " "

限制：
0 <= s 的长度 <= 50000

题目链接

Leetcode

题目解答

解法一

哈希表记录次数，使用一个数组把字符映射成数组下标，数组元素记录字符出现次数，遍历整个字符串就能得到所有字符出现的次数，然后按照原字符串中的顺序找出第一个出现次数是1的字符，如果找不到就返回空格。

时间复杂度:$O(n)$ 空间复杂度:$O(1)$

class Solution {
    public char firstUniqChar(String s) {
        char[] chs = s.toCharArray();
        int[] frequency = new int[26];
        for (char ch : chs) {
            frequency[ch - 'a']++;
        }
        for (char ch : chs) {
            if (frequency[ch - 'a'] == 1) {
                return ch;
            }
        }
        return ' ';
    }
}

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

解法二

哈希表记录位置，使用哈希表记录每个字符出现的位置，如果哈希表的 key 中不包含该字符就把字符和字符位置记录下来，否则字符出现多次，不满足题目要求，把字符的位置修改为 -1。遍历哈希表，找出其中位置不为 -1 的最小值，就是第一个只出现一次字符的所在位置。

时间复杂度:$O(n)$ 空间复杂度:$O(1)$

class Solution {
    public char firstUniqChar(String s) {
        Map<Character, Integer> map = new HashMap<>(32);
        int length = s.length();
        for (int i = 0; i < length; i++) {
            char ch = s.charAt(i);
            if (map.containsKey(ch)) {
                map.put(ch, -1);
            } else {
                map.put(ch, i);
            }
        }
        int first = length;
        for (char ch : map.keySet()) {
            int pos = map.get(ch);
            if (pos != -1 && pos < first) {
                first = pos;
            }
        }
        return first == length ? ' ' : s.charAt(first);
    }
}

执行用时：27 ms, 在所有 Java 提交中击败了54.80%的用户
内存消耗：38.6 MB, 在所有 Java 提交中击败了77.72%的用户

解法三

在解法一的基础上，使用队列在字符遍历过程中将首次出现的字符入队，遍历结束后，队列中的字符依次出队，如果字符统计的次数是1，那么这个字符就是第一个只出现一次的字符，返回即可。

时间复杂度:$O(n)$ 空间复杂度:$O(1)$

class Solution {
    public char firstUniqChar(String s) {
        LinkedList<Character> queue = new LinkedList<>();
        int[] frequency = new int[26];
        for (int i = 0; i < s.length(); i++) {
            char ch = s.charAt(i);
            frequency[ch - 'a']++;
            if (frequency[ch - 'a'] == 1) {
                queue.add(ch);
            }
        }
        while (!queue.isEmpty()) {
            char ch = queue.poll();
            if (frequency[ch - 'a'] == 1) {
                return ch;
            }
        }
        return ' ';
    }
}

执行用时：8 ms, 在所有 Java 提交中击败了81.60%的用户
内存消耗：38.6 MB, 在所有 Java 提交中击败了83.96%的用户