题目

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

思路1（哈希表）

• 先遍历一遍字符串，将字符串中的每个字符存入哈希表中，true代表只出现一次，false代表出现多次
• 统计结束后，然后再顺序遍历一遍字符串，查找哈希表，判断是否只出现一次

代码

class Solution {
    public char firstUniqChar(String s) {
        HashMap<Character, Boolean> map = new HashMap<>();

        char[] cs = s.toCharArray();
        int length = cs.length;

        // 将key添加到hashmap中，value用boolean值表示是否只出现一次
        for (int i = 0; i < length; i++) {
            // 如果存在key的话，存入false，否则存入true
            map.put(cs[i], !map.containsKey(cs[i]));
        }

        // 遍历每一个字符，查找map表，查看是否只出现一次
        for (int i = 0; i < length; i++) {
            if (map.get(cs[i])) {
                return cs[i];
            }
        }

        return ' ';
    }
}

复杂度分析

• 时间复杂度：\(O(N)\)
• 空间复杂度：\(O(1)\)，哈希表最多存储26个英文字符，所以忽略不计

思路2（有序哈希表）

• 因为哈希表是无序的，所以我们还得再遍历一次字符串判断。现在我们可以使用有序哈希表，这样子将字符串里面的字符都计算完之后我们直接再次遍历哈希表，找出第一次value为true的key即可

代码

class Solution {
    public char firstUniqChar(String s) {
        // 使用有序哈希表
        LinkedHashMap<Character, Boolean> map = new LinkedHashMap<>();

        char[] cs = s.toCharArray();
        int length = cs.length;

        for (int i = 0; i < length; i++) {
            map.put(cs[i], !map.containsKey(cs[i]));
        }

        // 找出第一个value为true的key
        for (Map.Entry<Character, Boolean> entry : map.entrySet()) {
            if (entry.getValue()) {
                return entry.getKey();
            }
        }

        return ' ';
    }
}

复杂度分析

• 时间复杂度：\(O(N)\)
• 空间复杂度：\(O(1)\)，哈希表最多存储26个英文字符，所以忽略不计