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

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

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

示例:

s = "abaccdeff"
返回 "b"

s = ""
返回 " "

限制：

0 <= s 的长度 <= 50000

一、数组

做题思路：这个思路其实当时面试的时候想出来的，算是暴力算法的感觉。

以s = "abaccdeff"为例，

a-a=0,arr[0]++

b-a=1,arr[1]++

......

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

二、哈希表

做题思路：我们可以对字符串进行两次遍历。

在第一次遍历时，我们使用哈希映射统计出字符串中每个字符出现的次数。在第二次遍历时，我们只要遍历到了一个只出现一次的字符，那么就返回该字符，否则在遍历结束后返回空格。

class Solution {
    public char firstUniqChar(String s) {
        Map frequency = new HashMap();
        for (int i = 0; i < s.length(); ++i) {
            char ch = s.charAt(i);
            //这里就是若frequency中的key含有ch则将ch对应的value加一，若不含ch则给键值ch对应的value赋默认值然后再 + 1.
            frequency.put(ch, frequency.getOrDefault(ch, 0) + 1);
        }
        for (int i = 0; i < s.length(); ++i) {
            if (frequency.get(s.charAt(i)) == 1) {
                return s.charAt(i);
            }
        }
        return ' ';
    }
}

这个是k神更简便的代码：

如果dic不包含key：c，则向dic添加健对（c,true),代表字符c的数量为1

如果dic包含key:c，则修改c的健对为(c,false),代表字符c的数量>1

class Solution {
    public char firstUniqChar(String s) {
        HashMap dic = new HashMap<>();
        char[] sc = s.toCharArray();
        for(char c : sc)
            dic.put(c, !dic.containsKey(c));
        for(char c : sc)
            if(dic.get(c)) return c;
        return ' ';
    }
}

三、有序哈希表

做题思路：

这个与上一个思路相比，使用了LinkedHashMap实现有序哈希表，然后在第二轮遍历的时候是比上一个思路的遍历进行遍历dic一轮，dic的长度是小于26的。

class Solution {
    public char firstUniqChar(String s) {
        Map dic = new LinkedHashMap<>();
        char[] sc = s.toCharArray();
        for(char c : sc)
            dic.put(c, !dic.containsKey(c));
        for(Map.Entry d : dic.entrySet()){
           if(d.getValue()) return d.getKey();
        }
        return ' ';
    }
}

参考链接：

1、https://leetcode-cn.com/problems/di-yi-ge-zhi-chu-xian-yi-ci-de-zi-fu-lcof/solution/di-yi-ge-zhi-chu-xian-yi-ci-de-zi-fu-by-3zqv5/

2、https://leetcode-cn.com/problems/di-yi-ge-zhi-chu-xian-yi-ci-de-zi-fu-lcof/solution/mian-shi-ti-50-di-yi-ge-zhi-chu-xian-yi-ci-de-zi-3/