LeetCode 每日一题 [64] 第一个只出现一次的字符

LeetCode 第一个只出现一次的字符 [简单]

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/di-yi-ge-zhi-chu-xian-yi-ci-de-zi-fu-lcof

示例:

s = "abaccdeff"
返回 "b"
s = ""
返回 " "

限制：

0 <= s 的长度 <= 50000

题目分析

解法1

双重for循环，暴力匹配 但是超时了

解法2

使用hash表，存储key - value 然后拿出数据进行比较，但是数据多了之后，就是产生很多的hash碰撞，效率低下

解法3

使用数组 字符的个数就是 256 所以可以创建 大小为256 的int数组来分别记录每个字符出现的个数 匹配之后子再次循环，匹配到第一个就返回

代码实现

public class FirstUniqChar {
    public static void main(String[] args) {
        String s = "sdnvlbkrmtbollujsdjfjf";
        System.out.println(firstUniqChar(s));
        System.out.println(firstUniqChar1(s));
        System.out.println(firstUniqChar2(s));
    }

    public static char firstUniqChar2(String s) {
        HashMap<Character, Boolean> 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 ' ';
    }

    public static char firstUniqChar1(String s) {
        int[] count = new int[256];
        char[] chars = s.toCharArray();
        for (char c : chars) {
            count[c]++;
        }
        for (char c : chars) {
            if (count[c] == 1) {
                return c;
            }
        }
        return ' ';
    }

    public static char firstUniqChar(String s) {
        if (s == null || s.length() == 0) {
            return ' ';
        }
        for (int i = 0; i < s.length(); i++) {
            int temp = 0;
            for (int j = 0; j < s.length(); j++) {
                if (s.charAt(i) == s.charAt(j)) {
                    temp++;
                }
            }
            if (temp == 1) {
                return s.charAt(i);
            }
            temp = 0;
        }
        return ' ';
    }
}