java - 使用哈希数组和 Java 8 流对字符串进行排序

Question

我在 GeeksforGeeks - Sort string of characters 上偶然发现了这个时间复杂度为 O(n) 的很酷的排序算法我试图重构代码以在嵌套的 for 循环中使用 Java Streams，并将结果收集到一个字符串变量中，但我似乎无法理解它。

原始代码如下:

// Java program to sort
// a string of characters
public class SortString{
    static final int MAX_CHAR = 26;
 
    // function to print string in sorted order
    static void sortString(String str) {
 
        // Hash array to keep count of characters.
        int letters[] = new int[MAX_CHAR];
 
        // Traverse string and increment
        // count of characters
        for (char x : str.toCharArray()) {
 
            // 'a'-'a' will be 0, 'b'-'a' will be 1,
            // so for location of character in count
            // array we will do str[i]-'a'.
            letters[x - 'a']++;
        }
        
        // HOW TO CONVERT THIS TO JAVA STREAM?  
        // Traverse the hash array and print
        // characters
        for (int i = 0; i < MAX_CHAR; i++) {
            for (int j = 0; j < letters[i]; j++) {
                System.out.print((char) (i + 'a'));
            }
        }
    }
 
    // Driver program to test above function
    public static void main(String[] args) {
        sortString("geeksforgeeks");
    }
}
// This code is contributed
// by Sinuhe

Answer 1

我们可以在 O(n) 时间内仅使用流对预期仅包含小写英文字母的给定字符串进行排序(无需使用预先计算的数组)通过使用 LinkedHashMap，它将在 collector 内部使用。

我们可以创建一个自定义收集器，它将使用静态方法Collector.of() 将流元素累积到LinkedHashMap 中。处理完整个字符串后，LinkedHashMap 将包含给定字符串中每个小写英文字母的频率，收集器 的finisher 函数 将将此映射转换为结果字符串。

public static void main(String[] args) {
    String str = "aewwawaeaea";

    String result = str.chars()
        .boxed()
        .collect(Collector.of(
            () -> IntStream.rangeClosed('a', 'z')
                .collect(LinkedHashMap::new, (map, next) -> map.put(next, 0), LinkedHashMap::putAll),
            (LinkedHashMap<Integer, Integer> map, Integer next) -> map.merge(next, 1, Integer::sum),
            (left, right) -> {
                right.forEach((k, v) -> left.merge(k, v, Integer::sum));
                return left;
            },
            map -> map.entrySet().stream()
                .map(entry -> Character.toString(entry.getKey()).repeat(entry.getValue()))
                .collect(Collectors.joining())
        ));
    
    System.out.println(result);
}

输出:

aaaaaeeewww

正如 @Holger 在 comments 中所建议的那样，我们可以基于 26 元素的 int 数组构建一个 collector。

collector 比前一个更简洁、性能更好:

public static void main(String[] args) {
    String str = "aewwawaeaea";
    String result = str.chars()
        .boxed()
        .collect(Collector.of(
            () -> new int['z' - 'a' + 1],
            (int[] arr, Integer next) -> arr[next - 'a']++,
            (left, right) -> {
                Arrays.setAll(left, i -> left[i] + right[i]);
                return left;
            },
            arr -> IntStream.range(0, arr.length)
                .mapToObj(i -> Character.toString(i + 'a').repeat(arr[i]))
                .collect(Collectors.joining())
        ));
    
    System.out.println(result);
}

输出:

aaaaaeeewww