比较字符串最小字母出现频次
难度:
标签:
题目描述
代码结果
运行时间: 36 ms, 内存: 16.5 MB
/*
* 思路:
* 1. 定义函数f(s)来计算字符串s中字典序最小字母的出现频次。
* 2. 使用Java Stream API来处理queries和words数组。
* 3. 对于每个查询queries[i],计算其f值,并统计满足f(queries[i]) < f(words[j])的词的数量。
* 4. 返回结果数组。
*/
import java.util.*;
import java.util.stream.*;
public class Solution {
public static int[] numSmallerByFrequency(String[] queries, String[] words) {
int[] wordFreqs = Arrays.stream(words).mapToInt(Solution::f).toArray();
return Arrays.stream(queries)
.mapToInt(query -> (int) Arrays.stream(wordFreqs)
.filter(wordFreq -> f(query) < wordFreq)
.count())
.toArray();
}
private static int f(String s) {
return s.chars()
.mapToObj(c -> (char) c)
.collect(Collectors.groupingBy(c -> c, Collectors.counting()))
.entrySet()
.stream()
.min(Map.Entry.comparingByKey())
.map(Map.Entry::getValue)
.orElse(0L)
.intValue();
}
public static void main(String[] args) {
String[] queries = {"cbd"};
String[] words = {"zaaaz"};
System.out.println(Arrays.toString(numSmallerByFrequency(queries, words)));
}
}
解释
方法:
此题解采用了前缀和的思想。首先,定义一个辅助函数 f(s),用于计算字符串 s 中按字典序最小的字母出现的次数。然后,对于词汇表 words 中的每个单词,计算其 f 值,并将对应的计数值加 1,存储在一个长度为 12 的数组 count 中,因为单词的最大长度为 10,所以 f 值的范围是 1 到 10。接着,从后往前对 count 数组进行累加,使得 count[i] 表示 f 值大于等于 i 的单词数量。最后,对于每个查询,通过查询 count 数组得到满足条件的单词数量。
时间复杂度:
O(nL + m)
空间复杂度:
O(m)
代码细节讲解
🦆
为什么在处理count数组时选择从后向前累加而不是从前向后?
▷🦆
在函数f中,为什么选择用'z'作为初始的ch变量,这里有没有其他字符作为起始值的可能性?
▷🦆
count数组长度为12的具体依据是什么,考虑到单词最大长度为10,为何不是长度为11?
▷🦆
在实际编码中,如何保证每个单词的长度都不超过10,是否有必要在输入时进行检查?
▷