我在 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
最佳答案
我们可以在 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
关于java - 使用哈希数组和 Java 8 流对字符串进行排序,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/72933808/