寻找字符串首个非重复字符超时，求O(n)/O(1)优化方案

问题描述 #

给定仅由字母组成的字符串s，返回首个非重复元素，若无则返回'-'。示例：输入s="abacabad"，输出'c'。
我写出的代码仅通过16/19测试用例，能否用O(n)或O(1)时间复杂度解决？

原代码 #

public char solution(String s) {
    ArrayList<Character> hs = new ArrayList<>();
    
    for (char c:s.toCharArray()) {
        hs.add(c);
    }
    
    for (int j=0; j<s.length(); j++) {
        if ( 1 == Collections.frequency(hs, s.charAt(j))) {
            return s.charAt(j);
        }
    }
    
    return '_';
}

原代码问题分析 #

1. 时间复杂度过高：Collections.frequency方法会遍历整个ArrayList统计指定字符的出现次数，外层循环又遍历字符串n次，整体时间复杂度为O(n²)，处理长字符串时会超时，这是未通过部分测试用例的核心原因。
2. 返回值不符合要求：题目要求无重复字符时返回'-'，但代码返回的是'_'，这也会导致部分测试用例失败。

O(n)与O(1)时间复杂度解法 #

解法1：HashMap统计法（O(n)时间，O(1)级空间） #

利用HashMap统计每个字符的出现次数，再遍历字符串找到首个次数为1的字符：

public char solution(String s) {
    HashMap<Character, Integer> countMap = new HashMap<>();
    // 第一次遍历统计字符出现次数
    for (char c : s.toCharArray()) {
        countMap.put(c, countMap.getOrDefault(c, 0) + 1);
    }
    // 第二次遍历找首个非重复字符
    for (char c : s.toCharArray()) {
        if (countMap.get(c) == 1) {
            return c;
        }
    }
    return '-';
}

• 时间复杂度：O(n)，两次线性遍历字符串，HashMap的存取操作平均为O(1)。
• 空间复杂度：O(k)，k为字符串中不同字符的数量，对于英文字母来说最多52个（大小写），空间消耗接近O(1)。

解法2：数组统计法（O(n)时间，严格O(1)空间） #

由于输入仅为字母，可使用固定大小的数组替代HashMap，进一步优化空间：

public char solution(String s) {
    int[] count = new int[256]; // 覆盖所有ASCII字母
    // 统计字符出现次数
    for (char c : s.toCharArray()) {
        count[c]++;
    }
    // 查找首个非重复字符
    for (char c : s.toCharArray()) {
        if (count[c] == 1) {
            return c;
        }
    }
    return '-';
}

• 时间复杂度：O(n)，两次线性遍历，效率与HashMap解法相当。
• 空间复杂度：O(1)，数组大小固定为256，不随输入字符串长度变化。

内容的提问来源于stack exchange，提问作者Yunmi Lee