LeetCode 1170中等二分查找
比较字符串最小字母出现频次 图解题解
这道题到底在问什么
给两个字符串数组 queries 和 words。f(s) 定义为 s 中字典序最小字母的出现次数。对每个查询 queries[i],统计 words 里有多少个词 w 满足 f(queries[i]) 严格小于 f(w),把这些结果按顺序组成答案数组返回。
- 输入
- queries=["cbd"], words=["zaaaz"]
- 输出
- [1]
- 输入
- queries=["bbb","cc"], words=["a","aa","aaa","aaaa"]
- 输出
- [1,2]
最优解：一步一步想明白
- 3记牢三步:先把每个词的 f 算出来,再排序,最后对每个查询二分找第一个更大的位置。下面每一帧都在套这三步。
- 4下面这排是 words 里的五个词。右边面板要记每个词的 f 值,现在都还是问号。咱们从左到右,一个词一个词地算:先找它字典序最小的字母,再数这个字母出现几次。
- 5看第 0 个词 "abb"。它里面字典序最小的字母是 a,数一数 a 一共出现了 1 次,所以 f("abb") = 1。把这个值记到右边面板。
- 6看第 1 个词 "cc"。它里面字典序最小的字母是 c,数一数 c 一共出现了 2 次,所以 f("cc") = 2。把这个值记到右边面板。
- 7看第 2 个词 "dddd"。它里面字典序最小的字母是 d,数一数 d 一共出现了 4 次,所以 f("dddd") = 4。把这个值记到右边面板。
- 8看第 3 个词 "aa"。它里面字典序最小的字母是 a,数一数 a 一共出现了 2 次,所以 f("aa") = 2。把这个值记到右边面板。
- 9看第 4 个词 "e"。它里面字典序最小的字母是 e,数一数 e 一共出现了 1 次,所以 f("e") = 1。把这个值记到右边面板。
- 10五个词的 f 全算完,从左到右是 1、2、4、2、1。注意这里现在装的不再是词,而是它们各自的 f 值。词本身已经用不上了,接下来只跟这排数字打交道。
- 11现在这排 f 是乱的:1、2、4、2、1。要做二分,前提是有序,所以先把它从小到大排好。排序这一步是为后面每次查询都能快速二分做准备,只排这一次。
- 12排好了,从小到大是 1、1、2、2、4。有了这个有序数组,后面每来一个查询,都能用二分快速数出有几个比它大,不用每次从头扫一遍。
- 13底下这排有序的词 f = 1、1、2、2、4 接下来一直不变。每来一个查询,先算它自己的 f,再在这排数里找第一个比它大的位置,从那里到末尾的个数就是答案。
- 14轮到第 0 个查询 "bbb"。先算它的 f:最小字母是 b,出现 3 次,所以 f("bbb") = 3。现在的任务,是在底下有序的 1、1、2、2、4 里,数出有几个数比 3 大。
- 15当前搜索区间 [0, 5) 的中点是 sorted[2] = 2。它不比 3 大,那它和它左边的都不够大,灰掉排除,往它右边找。绿色这段是已经确认比 3 大的词。
- 16当前搜索区间 [3, 5) 的中点是 sorted[4] = 4。它比 3 大,那它和它右边的都更大,记成绿色,继续往它左边找有没有更小的、也比 3 大的。绿色这段是已经确认比 3 大的词。
- 17当前搜索区间 [3, 4) 的中点是 sorted[3] = 2。它不比 3 大,那它和它左边的都不够大,灰掉排除,往它右边找。绿色这段是已经确认比 3 大的词。
- 18二分停下来,第一个比 3 大的位置是下标 4。从这里到末尾一共 1 个数,它们全都比 3 大,所以查询 "bbb" 的答案就是 1。绿色那段就是数出来的更大的词。
- 19轮到第 1 个查询 "a"。先算它的 f:最小字母是 a,出现 1 次,所以 f("a") = 1。现在的任务,是在底下有序的 1、1、2、2、4 里,数出有几个数比 1 大。
- 20当前搜索区间 [0, 5) 的中点是 sorted[2] = 2。它比 1 大,那它和它右边的都更大,记成绿色,继续往它左边找有没有更小的、也比 1 大的。绿色这段是已经确认比 1 大的词。
- 21当前搜索区间 [0, 2) 的中点是 sorted[1] = 1。它不比 1 大,那它和它左边的都不够大,灰掉排除,往它右边找。绿色这段是已经确认比 1 大的词。
- 22二分停下来,第一个比 1 大的位置是下标 2。从这里到末尾一共 3 个数,它们全都比 1 大,所以查询 "a" 的答案就是 3。绿色那段就是数出来的更大的词。
- 23轮到第 2 个查询 "eeee"。先算它的 f:最小字母是 e,出现 4 次,所以 f("eeee") = 4。现在的任务,是在底下有序的 1、1、2、2、4 里,数出有几个数比 4 大。
- 24当前搜索区间 [0, 5) 的中点是 sorted[2] = 2。它不比 4 大,那它和它左边的都不够大,灰掉排除,往它右边找。绿色这段是已经确认比 4 大的词。
- 25当前搜索区间 [3, 5) 的中点是 sorted[4] = 4。它不比 4 大,那它和它左边的都不够大,灰掉排除,往它右边找。绿色这段是已经确认比 4 大的词。
- 26二分停下来,第一个比 4 大的位置是下标 5。从这里到末尾一共 0 个数,它们全都比 4 大,所以查询 "eeee" 的答案就是 0。绿色那段就是数出来的更大的词。
- 27三个查询都数完了。"bbb" 的 f 是 3,比它大的只有 4 一个,答案 1;"a" 的 f 是 1,比它大的有 2、2、4 三个,答案 3;"eeee" 的 f 是 4,没有比它更大的,答案 0。最终答案数组是 [1, 3, 0]。
⚠️ 容易写错的地方
✗ 错：把 f 理解成「最小字母」本身或「不同字母个数」
✓ 对：f 是字典序最小那个字母的出现次数
f("dcce") 最小字母是 c,c 出现 2 次,所以 f 是 2,不是字母 c、也不是 3 种字母
✗ 错：查询要的是「相等或更大」
✓ 对：题目要严格更大,f(query) 严格小于 f(word) 才算
相等不计入,所以二分找的是第一个严格大于 x 的位置
✗ 错：没排序就想二分计数
✓ 对：必须先把词的 f 从小到大排好
二分依赖有序,乱序里「右边都更大」这个前提不成立
完整代码（Python / C++ / Java）
Python
from __future__ import annotations
from 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 = right
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class 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]C++
#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <optional>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode() : val(0), left(nullptr), right(nullptr) {}
TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
};
struct ListNode {
int val;
ListNode *next;
ListNode() : val(0), next(nullptr) {}
ListNode(int x) : val(x), next(nullptr) {}
ListNode(int x, ListNode *next) : val(x), next(next) {}
};
class Solution {
public:
vector<int> numSmallerByFrequency(vector<string>& queries, vector<string>& words) {
auto f = [](string s) {
int cnt[26] = {0};
for (char c : s) {
cnt[c - 'a']++;
}
for (int x : cnt) {
if (x) {
return x;
}
}
return 0;
};
int n = words.size();
int nums[n];
for (int i = 0; i < n; i++) {
nums[i] = f(words[i]);
}
sort(nums, nums + n);
vector<int> ans;
for (auto& q : queries) {
int x = f(q);
ans.push_back(n - (upper_bound(nums, nums + n, x) - nums));
}
return ans;
}
};Java
import java.util.*;
class TreeNode { int val; TreeNode left; TreeNode right; TreeNode(){} TreeNode(int val){this.val=val;} TreeNode(int val, TreeNode left, TreeNode right){this.val=val;this.left=left;this.right=right;} }
class ListNode { int val; ListNode next; ListNode(){} ListNode(int val){this.val=val;} ListNode(int val, ListNode next){this.val=val;this.next=next;} }
class Solution {
public int[] numSmallerByFrequency(String[] queries, String[] words) {
int n = words.length;
int[] nums = new int[n];
for (int i = 0; i < n; ++i) {
nums[i] = f(words[i]);
}
Arrays.sort(nums);
int m = queries.length;
int[] ans = new int[m];
for (int i = 0; i < m; ++i) {
int x = f(queries[i]);
int l = 0, r = n;
while (l < r) {
int mid = (l + r) >> 1;
if (nums[mid] > x) {
r = mid;
} else {
l = mid + 1;
}
}
ans[i] = n - l;
}
return ans;
}
private int f(String s) {
int[] cnt = new int[26];
for (int i = 0; i < s.length(); ++i) {
++cnt[s.charAt(i) - 'a'];
}
for (int x : cnt) {
if (x > 0) {
return x;
}
}
return 0;
}
}复杂度
时间
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)
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 比较字符串最小字母出现频次 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么要先排序再二分,直接对每个查询扫一遍词不行吗?+
直接扫当然也能算,每个查询扫一遍 n 个词,m 个查询就是 O(n·m)。先把词的 f 排好序,只排一次 O(n log n),之后每个查询二分只要 O(log n),m 个查询总共 O(m log n)。当查询数和词数都很大时,排序加二分明显更快,这是用一次预处理换后面每次查询都快的典型思路。
算 f 时怎么快速拿到字典序最小的字母?+
不用真排序整个字符串。开一个长度 26 的计数数组,扫一遍把每个字母计数,然后从下标 0 也就是字母 a 开始往后找,第一个计数大于 0 的下标就对应字典序最小的字母,它的计数就是 f。这样算一个 f 是 O(L),L 是字符串长度。
如果查询非常多,还能再优化吗?+
可以把有序词 f 进一步压成「后缀计数」或前缀和:因为 f 的取值范围很小(字符串长度有限,f 不会超过最长词的长度),可以开一个桶记每个 f 值有几个,再做一遍后缀和,查询时直接查表 O(1) 拿到「比 x 大的有几个」,连二分的 log 都省了。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 比较字符串最小字母出现频次 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。