如何基于哈希数组使用Java 8 Streams实现O(n)复杂度字符排序

API 探路者

2026-8-27

实现方案

你要实现的是仅包含小写英文字母的字符串线性时间排序，核心是把原有遍历计数数组拼接结果的嵌套for循环改为Java Stream写法，同时将结果收集为字符串返回，全程保留原算法*O(n)*的时间复杂度。

原逻辑的核心是按a-z的顺序，根据每个字符的出现次数重复拼接对应字符，用Stream实现时可以直接按索引遍历长度为26的计数数组，按频次生成对应字符序列后聚合即可。

重构后完整代码

import java.util.stream.Collectors;
import java.util.stream.IntStream;

public class SortString{
    static final int MAX_CHAR = 26;
 
    static String sortString(String str) {
        int[] letters = new int[MAX_CHAR];
        // 统计各字符出现频次
        for (char x : str.toCharArray()) {
            letters[x - 'a']++;
        }
        
        // 原嵌套循环的Stream实现
        return IntStream.range(0, MAX_CHAR)
                .mapToObj(i -> String.valueOf((char) (i + 'a')).repeat(letters[i]))
                .collect(Collectors.joining());
    }
 
    public static void main(String[] args) {
        // 测试输入geeksforgeeks，输出结果为eeeefggkkorss
        System.out.println(sortString("geeksforgeeks"));
    }
}

兼容说明

上述代码用了Java 11新增的String.repeat()方法生成重复字符，如果是Java 10及以下版本，可以替换为嵌套Stream生成重复序列，逻辑完全等价：

return IntStream.range(0, MAX_CHAR)
        .mapToObj(i -> IntStream.range(0, letters[i])
                .mapToObj(j -> String.valueOf((char) (i + 'a')))
                .collect(Collectors.joining()))
        .collect(Collectors.joining());

如果希望把前面的字符计数逻辑也改成Stream写法，可以替换原有计数循环为如下实现，性能和原生数组遍历接近：

int[] letters = str.chars()
        .map(c -> c - 'a')
        .collect(
                () -> new int[MAX_CHAR],
                (arr, idx) -> arr[idx]++,
                (arr1, arr2) -> {}
        );