力扣---剑指 Offer 50. 第一个只出现一次的字符-526互联

在字符串 s 中找出第一个只出现一次的字符。如果没有，返回一个单空格。 s 只包含小写字母。
示例 1:
输入：s = "abaccdeff"
输出：'b'

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

限制：
0 <= s 的长度 <= 50000
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/di-yi-ge-zhi-chu-xian-yi-ci-de-zi-fu-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

一开始想到了利用哈希表的两次遍历解法。之后想到可以利用队列先进先出的特点。结果写出来的时间占用惨不忍睹。。。

队列：

class Solution {
    public char firstUniqChar(String s) {
        Map<Character, Integer> map = new HashMap<>();
        Queue<Character> queue = new LinkedList<>();
        for (char c : s.toCharArray()) {
            if (map.containsKey(c)) {
                map.put(c, map.get(c) + 1);
                while (!queue.isEmpty()) {
                    char tem = queue.peek();
                    if (map.get(tem) == 1) {
                        break;
                    } else {
                        queue.remove();
                    }
                }
            } else {
                queue.add(c);
                map.put(c, map.getOrDefault(c, 0) + 1);
            }
        }
        return queue.isEmpty() ? ' ' : queue.peek();
    }
}

哈希表两次遍历：

第一种：

class Solution {
    public char firstUniqChar(String s) {
        Map<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < s.length(); i ++) {
            if (map.containsKey(s.charAt(i))) {
                map.put(s.charAt(i), -1);
            } else {
                map.put(s.charAt(i), i);
            }
        }
        int res = Integer.MAX_VALUE;
        for (Map.Entry<Character, Integer> entry : map.entrySet()) {
            if (entry.getValue() != -1) {
                res = Math.min(res, entry.getValue());
            }
        }
        return res == Integer.MAX_VALUE ? ' ' : s.charAt(res);
    }
}

第二种：

class Solution {
    public char firstUniqChar(String s) {
        Map<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < s.length(); i ++) {
            char tem = s.charAt(i);
            map.put(tem, map.getOrDefault(tem, 0) + 1);
        }
        for (char c : s.toCharArray()) {
            if (map.get(c) == 1) {
                return c;
            }
        }
        return ' ';
    }
}

也可以利用LinkedMap保持插入顺序的特点：

class Solution {
    public char firstUniqChar(String s) {
        Map<Character, Integer> map = new LinkedHashMap<>();
        for (int i = 0; i < s.length(); i ++) {
            map.put(s.charAt(i), map.getOrDefault(s.charAt(i), 0) + 1);
        }
        char res = ' ';
        for (Map.Entry<Character, Integer> entry : map.entrySet()) {
            if (entry.getValue() == 1) {
                res = entry.getKey();
                break;
            }
        }
        return res;
    }
}