用哈希表辅助查找

题目链接-来源：力扣（LeetCode）

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

示例:

s = “abaccdeff”
返回 “b”

s = “”
返回 “ “

思路：

遍历字符串，将出现过的字符存入哈希表中，并配以一个 boolean 状态值记录其是否只出现过一次。再次出现以后就将这个值改为 false。完成以后我们再次遍历字符串，找到键值为 true 的字符返回即可。否则返回 ‘ ‘。
进一步优化：
若语言支持有序哈希表，则第二步只需遍历哈希表。
时间复杂度：O(n)
空间复杂度：O(1)

实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public char firstUniqChar(String s) {
        int n = s.length();
        Map<Character, Boolean> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            if (map.containsKey(c)) {
                map.put(c, false);
            } else {
                map.put(c, true);
            }
        }
        for (int i = 0; i < n; i++) {
            char c = s.charAt(i);
            if (map.get(c)) {
                return c;
            }
        }
        return ' ';
    }
}