题目描述
我们来定义一个函数 f(s)
,其中传入参数 s
是一个非空字符串;该函数的功能是统计 s
中(按字典序比较)最小字母的出现频次。
例如,若 s = "dcce"
,那么 f(s) = 2
,因为最小的字母是 "c"
,它出现了 2 次。
现在,给你两个字符串数组待查表 queries
和词汇表 words
,请你返回一个整数数组 answer
作为答案,其中每个 answer[i]
是满足 f(queries[i]) < f(W)
的词的数目,W
是词汇表 words
中的词。
样例
输入:queries = ["cbd"], words = ["zaaaz"]
输出:[1]
解释:查询 f("cbd") = 1,而 f("zaaaz") = 3 所以 f("cbd") < f("zaaaz")。
输入:queries = ["bbb","cc"], words = ["a","aa","aaa","aaaa"]
输出:[1,2]
解释:第一个查询 f("bbb") < f("aaaa"),第二个查询 f("aaa") 和 f("aaaa") 都 > f("cc")。
限制
1 <= queries.length <= 2000
1 <= words.length <= 2000
1 <= queries[i].length, words[i].length <= 10
queries[i][j], words[i][j]
都是小写英文字母
算法
(枚举,后缀和) $O((n + m)L)$
- 创建一个
sum
数组,位置i
记录大于等于频率i
单词的个数。将所有words
中的单词求出对应的频率,假设words[i]
的频率是x
,则sum[x]++
。 - 然后从 10 到 1,更新
sum
数组的后缀和。 - 对于每个询问,求出频率为
y
后,sum[y + 1]
就是答案。
时间复杂度
- 预处理的时间复杂度为 $O(mL)$,这里的 $m$ 是词汇表总单词的个数,$L$ 是单词的最大长度。预处理
sum
的时间复杂度为 $O(L)$。 - 共有 $n$ 个询问,对于每个询问,仅需要 $O(L)$ 的时间求出频率,然后 $O(1)$ 的时间得到答案。
- 故总时间复杂度为 $O((n + m)L)$。
空间复杂度
- 需要额外 $O(L)$ 的空间记录后缀和。
C++ 代码
class Solution {
public:
int calc_fre(const string &w) {
int tot = 0;
char min_c = w[0];
for (auto c : w) {
if (c < min_c) {
min_c = c;
tot = 1;
} else if (c == min_c) {
tot++;
}
}
return tot;
}
vector<int> numSmallerByFrequency(vector<string>& queries, vector<string>& words) {
vector<int> sum(12, 0);
for (const auto &w : words)
sum[calc_fre(w)]++;
for (int i = 10; i >= 1; i--)
sum[i] += sum[i + 1];
int n = queries.size();
vector<int> ans(n);
for (int i = 0; i < n; i++)
ans[i] = sum[calc_fre(queries[i]) + 1];
return ans;
}
};