题目描述

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

题解一

最直观的想法双重循环遍历。扫描字符串中的每个字符，查看是否有其他字符与其重复，输出第一个不重复的字符。

时间复杂度为O(n^2)，空间复杂度为O(1)。

public int FirstNotRepeatingChar(String str) {
    int index = -1;
    for (int i = 0; i < str.length(); i++) {
        boolean single = true;
        for (int j = 0; j < str.length(); j++) {
            if (j != i && str.charAt(i) == str.charAt(j)) {
                single = false;
                break;
            }
        }
        if (single) {
            index = i;
            break;
        }
    }
    return index;
}

题解二

基于哈希表实现，第一遍遍历统计每个字符出现的次数，第二遍遍历找出第一个只出现一次的字符。由于字符种类有限，故哈希表长度是有限的。

时间复杂度为O(n)，空间复杂度为O(1)。

class Solution {
    public char firstUniqChar(String s) {
        if ("".equals(s))
            return ' ';
        Map<Character, Integer> map = new HashMap<>();
        char[] chars = s.toCharArray();
        for (char ch : chars) {
            if (!map.containsKey(ch)) {
                map.put(ch, 1);
            } else map.put(ch, map.get(ch)+1);
        }
        for (char ch : chars) {
            if (map.get(ch) == 1)
                return ch;
        }
        return ' ';
    }
}