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

题目描述

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

示例

s = "abaccdeff"
返回 "b"

s = "" 
返回 " "

解题思路1

跟leetcode387差不多，只是返回值不一样，稍加修改就可以提交了。
用数组自创哈希表，因为只有小写字母，所以设置一个26长度的数组，字符串中出现一次，数组里对应的字母就+1，然后再对字符串的字母一一对照，如果值为1就输出，找不到1则无解。

代码1

class Solution {
    public char firstUniqChar(String s) {
       int[] count = new int[26]; // 因为都是小写字母，所以数组取26
        char[] chars = s.toCharArray(); 
        for(char c : chars){
            count[c-'a']++; // 因为是ASCII码字母出现一次+1
        }
        for(int i = 0;i<s.length();i++){
            if(count[s.charAt(i)-'a'] == 1){
                return s.charAt(i); // 找出只出现一次的字母
            }
        }
        return ' '; // 无解
    }
}

解题思路2

除去用数组做，第一印象肯定是HashMap，但是其结果却不尽人意。
究其原因，HashMap是由一个链表组成，其查找速度必然不如O(1)的数组，但是在插入和删除操作的时候，其查找速度比数组快。

代码2

class Solution {
    public char firstUniqChar(String s) {
        // 数组为空，返回空
        if(s.isEmpty()) return ' ';
        HashMap<Character, Integer> map = new HashMap<>();
        char c = ' ';
        // 遍历字符串，分别放入HashMap，第一次放入则值为0
        // 而后出现相同的时候取出Key对应的value，然后将value+1，放回Key对应的value中
        for(int i = 0;i < s.length(); i++){
            c = s.charAt(i);
            if(!map.containsKey(c)){
                map.put(c, 0);
            }else{
                // map.put(c, 1);
                int v = map.get(c);
                // map.remove(c);
                v++;
                map.put(c, v);
            }
        }
        // 
        for(int i = 0;i < s.length(); i++){
            c = s.charAt(i);
            if (map.get(c) == 0) {
                return c;
            }
        }
        return ' ';
    }
}