题目描述
思路解析动画文字版
记牢三步:先把每个词的 f 算出来,再排序,最后对每个查询二分找第一个更大的位置。下面每一帧都在套这三步。
阶段一 · 算每个词的 f：下面这排是 words 里的五个词。右边面板要记每个词的 f 值,现在都还是问号。咱们从左到右,一个词一个词地算:先找它字典序最小的字母,再数这个字母出现几次。
算 f · 第 0 个词 abb：看第 0 个词 "abb"。它里面字典序最小的字母是 a,数一数 a 一共出现了 1 次,所以 f("abb") = 1。把这个值记到右边面板。
算 f · 第 1 个词 cc：看第 1 个词 "cc"。它里面字典序最小的字母是 c,数一数 c 一共出现了 2 次,所以 f("cc") = 2。把这个值记到右边面板。
算 f · 第 2 个词 dddd：看第 2 个词 "dddd"。它里面字典序最小的字母是 d,数一数 d 一共出现了 4 次,所以 f("dddd") = 4。把这个值记到右边面板。
算 f · 第 3 个词 aa：看第 3 个词 "aa"。它里面字典序最小的字母是 a,数一数 a 一共出现了 2 次,所以 f("aa") = 2。把这个值记到右边面板。
算 f · 第 4 个词 e：看第 4 个词 "e"。它里面字典序最小的字母是 e,数一数 e 一共出现了 1 次,所以 f("e") = 1。把这个值记到右边面板。
阶段一完成 · 得到词的 f 数组：五个词的 f 全算完,从左到右是 1、2、4、2、1。注意这里现在装的不再是词,而是它们各自的 f 值。词本身已经用不上了,接下来只跟这排数字打交道。
阶段二 · 把词的 f 排序：现在这排 f 是乱的:1、2、4、2、1。要做二分,前提是有序,所以先把它从小到大排好。排序这一步是为后面每次查询都能快速二分做准备,只排这一次。
阶段二完成 · 有序的词 f 数组：排好了,从小到大是 1、1、2、2、4。有了这个有序数组,后面每来一个查询,都能用二分快速数出有几个比它大,不用每次从头扫一遍。
阶段三 · 逐个处理查询：底下这排有序的词 f = 1、1、2、2、4 接下来一直不变。每来一个查询,先算它自己的 f,再在这排数里找第一个比它大的位置,从那里到末尾的个数就是答案。
查询 0 · 算 f("bbb")：轮到第 0 个查询 "bbb"。先算它的 f:最小字母是 b,出现 3 次,所以 f("bbb") = 3。现在的任务,是在底下有序的 1、1、2、2、4 里,数出有几个数比 3 大。
查询 0 二分 · 看中点 2：当前搜索区间 [0, 5) 的中点是 sorted[2] = 2。它不比 3 大,那它和它左边的都不够大,灰掉排除,往它右边找。绿色这段是已经确认比 3 大的词。
查询 0 二分 · 看中点 4：当前搜索区间 [3, 5) 的中点是 sorted[4] = 4。它比 3 大,那它和它右边的都更大,记成绿色,继续往它左边找有没有更小的、也比 3 大的。绿色这段是已经确认比 3 大的词。
查询 0 二分 · 看中点 3：当前搜索区间 [3, 4) 的中点是 sorted[3] = 2。它不比 3 大,那它和它左边的都不够大,灰掉排除,往它右边找。绿色这段是已经确认比 3 大的词。
查询 0 · 结果 1：二分停下来,第一个比 3 大的位置是下标 4。从这里到末尾一共 1 个数,它们全都比 3 大,所以查询 "bbb" 的答案就是 1。绿色那段就是数出来的更大的词。
查询 1 · 算 f("a")：轮到第 1 个查询 "a"。先算它的 f:最小字母是 a,出现 1 次,所以 f("a") = 1。现在的任务,是在底下有序的 1、1、2、2、4 里,数出有几个数比 1 大。
查询 1 二分 · 看中点 2：当前搜索区间 [0, 5) 的中点是 sorted[2] = 2。它比 1 大,那它和它右边的都更大,记成绿色,继续往它左边找有没有更小的、也比 1 大的。绿色这段是已经确认比 1 大的词。
查询 1 二分 · 看中点 1：当前搜索区间 [0, 2) 的中点是 sorted[1] = 1。它不比 1 大,那它和它左边的都不够大,灰掉排除,往它右边找。绿色这段是已经确认比 1 大的词。
查询 1 · 结果 3：二分停下来,第一个比 1 大的位置是下标 2。从这里到末尾一共 3 个数,它们全都比 1 大,所以查询 "a" 的答案就是 3。绿色那段就是数出来的更大的词。
查询 2 · 算 f("eeee")：轮到第 2 个查询 "eeee"。先算它的 f:最小字母是 e,出现 4 次,所以 f("eeee") = 4。现在的任务,是在底下有序的 1、1、2、2、4 里,数出有几个数比 4 大。
查询 2 二分 · 看中点 2：当前搜索区间 [0, 5) 的中点是 sorted[2] = 2。它不比 4 大,那它和它左边的都不够大,灰掉排除,往它右边找。绿色这段是已经确认比 4 大的词。
查询 2 二分 · 看中点 4：当前搜索区间 [3, 5) 的中点是 sorted[4] = 4。它不比 4 大,那它和它左边的都不够大,灰掉排除,往它右边找。绿色这段是已经确认比 4 大的词。
查询 2 · 结果 0：二分停下来,第一个比 4 大的位置是下标 5。从这里到末尾一共 0 个数,它们全都比 4 大,所以查询 "eeee" 的答案就是 0。绿色那段就是数出来的更大的词。
完成 · 答案 [1, 3, 0]：三个查询都数完了。"bbb" 的 f 是 3,比它大的只有 4 一个,答案 1;"a" 的 f 是 1,比它大的有 2、2、4 三个,答案 3;"eeee" 的 f 是 4,没有比它更大的,答案 0。最终答案数组是 [1, 3, 0]。
边界先想清:f 相等时不计入(严格更大)、没有更大的返回 0、词全比查询大就全数上。
面试重点:排序加二分是「预处理换查询快」、用 26 长计数数组取最小字母、值域小还能用后缀计数做到查询 O(1)。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *from string import *from operator import *class TreeNode: def __init__(self, val=0, left=None, right=None): self.val = val self.left = left self.right = rightclass ListNode: def __init__(self, val=0, next=None): self.val = val self.next = nextclass Solution: def numSmallerByFrequency(self, queries: List[str], words: List[str]) -> List[int]: def f(s: str) -> int: cnt = Counter(s) return next(cnt[c] for c in ascii_lowercase if cnt[c]) n = len(words) nums = sorted(f(w) for w in words) return [n - bisect_right(nums, f(q)) for q in queries]复杂度
- 时间：O((n+m)·L + (n+m)·log n)，n 是词数,m 是查询数,L 是字符串平均长度。算所有 f 是 O((n+m)·L);对 n 个词 f 排序是 O(n log n);每个查询二分是 O(log n),m 个查询共 O(m log n)
- 空间：O(n)，存 n 个词的 f 数组是 O(n);C++ 与 Java 的 f 用固定 26 长计数数组是 O(1);排序内部 C++ 与 Java 递归栈约 O(log n),Python 的 sort 最坏 O(n),按峰值整体记 O(n)
易错点
面试追问把动画讲成自己的话
追问为什么要先排序再二分,直接对每个查询扫一遍词不行吗?
追问算 f 时怎么快速拿到字典序最小的字母?
追问如果查询非常多,还能再优化吗?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
元素和小于等于阈值的正方形的最大边长
LeetCode 1292 · 中等 · 沿着 二分套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题