自定义字符串排序
难度:
标签:
题目描述
代码结果
运行时间: 20 ms, 内存: 0.0 MB
/*
题目思路:
1. 使用 HashMap 存储 order 中字符的顺序。
2. 将 s 字符串转换为流,按顺序和不按顺序分类。
3. 按照 order 中的顺序排序后与未排序部分结合。
*/
import java.util.*;
import java.util.stream.*;
public class CustomSortString {
public String customSortString(String order, String s) {
// 存储 order 中字符的顺序
Map<Character, Integer> orderMap = new HashMap<>();
for (int i = 0; i < order.length(); i++) {
orderMap.put(order.charAt(i), i);
}
// 使用 Java Stream API 处理字符分类和排序
String result = s.chars()
.mapToObj(c -> (char) c)
.sorted(Comparator.comparingInt(c -> orderMap.getOrDefault(c, Integer.MAX_VALUE)))
.map(String::valueOf)
.collect(Collectors.joining());
return result;
}
}
解释
方法:
题解的思路是首先使用collections.Counter统计字符串T中各字符的出现频次。然后,按照字符串S(order)给定的顺序,从计数器中取出相应字符,并构建结果字符串。这确保了S中的字符在结果中的顺序是正确的。如果T中有字符不在S中,这些字符将保留在Counter中。最后,将剩余的字符按其原有频次添加到结果字符串的末尾。这样,S中未提及的字符将按T中的出现顺序排列。
时间复杂度:
O(n)
空间复杂度:
O(1)
代码细节讲解
🦆
在解决方案中,为什么要使用`collections.Counter`来统计`s`中的字符频率而不是其他数据结构?
▷🦆
算法在处理不在`order`中但存在于`s`中的字符时,是如何保证这些字符的相对顺序不变的?
▷🦆
代码中使用`ct.pop(s)`而不是`ct[s]`,这样做有什么特别的意图或优势?
▷🦆
如果`order`中包含的字符在`s`中并不出现,这种情况是否会影响到最终结果字符串的构建?
▷