求字符出现次数统计的更低时间复杂度解法（Monjim面试题）

你的现有写法虽然嵌套了循环，但实际每个字符仅被访问一次，理论时间复杂度其实是 O(n)，不过存在字符串拼接效率低、循环逻辑冗余的问题。我们可以通过一次遍历+可变字符串容器实现更高效且逻辑清晰的解法，严格保证 O(n) 时间复杂度。

核心优化点 #

• 用StringBuilder替代String直接拼接：String是不可变对象，每次+=都会生成新实例，带来额外开销；StringBuilder的追加操作是均摊 O(1) 时间。
• 简化遍历逻辑：单指针遍历，记录当前字符与连续计数，遇到不同字符时立即写入结果，避免嵌套循环的控制混乱。

优化后代码 #

private static String wordCount(String word) {
    if (word == null || word.isEmpty()) {
        return "";
    }
    
    StringBuilder result = new StringBuilder();
    char currentChar = word.charAt(0);
    int count = 1;
    
    for (int i = 1; i < word.length(); i++) {
        char c = word.charAt(i);
        if (c == currentChar) {
            count++;
        } else {
            result.append(currentChar).append(count);
            currentChar = c;
            count = 1;
        }
    }
    // 处理最后一组未写入的连续字符
    result.append(currentChar).append(count);
    
    return result.toString();
}

复杂度说明 #

• 时间复杂度：O(n)，仅需一次遍历字符串，每个字符仅访问一次，所有追加操作均为均摊常数时间。
• 空间复杂度：O(n)，StringBuilder存储结果，最坏情况（所有字符都不重复）下结果长度为 2n，属于线性空间。

原代码的问题补充 #

你的原代码中i=k的操作存在边界风险（当k等于字符串长度时，循环直接终止，可能遗漏最后一组字符的写入），且String拼接的隐性开销会让实际运行效率远低于理论值。

内容的提问来源于stack exchange，提问作者Madhukar H