1. 问题背景与核心思路LeetCode 1170题比较字符串最小字母出现频次是一道结合字符串处理和二分查找的经典题目。题目要求我们对于每个查询字符串统计words数组中满足条件的字符串数量。这类问题在实际工程中也很常见比如在搜索引擎的自动补全、数据过滤等场景都会用到类似的比较逻辑。我第一次做这道题时直接暴力解法导致超时。后来发现通过预处理二分查找的组合可以完美解决。预处理阶段将计算好的结果存储起来查询阶段就能以对数时间复杂度快速响应。这种空间换时间的策略在算法优化中非常实用。2. 预处理阶段详解2.1 最小字母频次计算首先需要定义一个函数来计算字符串的最小字母出现频次。这里有几个关键点需要注意def get_freq(word): if not word: # 处理空字符串情况 return 0 min_char min(word) # 找到最小字母 return word.count(min_char) # 统计最小字母出现次数注意min()函数在Python中会按照字母表顺序找到最小的字符a b ... z。对于非字母字符需要特别注意题目要求。2.2 预处理words数组我们需要预先计算words数组中每个字符串的最小字母频次并排序freqs sorted([get_freq(word) for word in words])排序是为了后续能够使用二分查找。时间复杂度O(n log n)空间复杂度O(n)。3. 二分查找实现3.1 查询处理流程对于每个查询字符串q计算q的最小字母频次f_q get_freq(q)在预处理好的freqs数组中找到第一个大于f_q的元素的索引满足条件的字符串数量就是数组长度减去这个索引3.2 二分查找实现细节Python的bisect模块提供了bisect_right函数可以直接使用import bisect def num_smaller(freqs, target): return len(freqs) - bisect.bisect_right(freqs, target)如果自己实现二分查找需要注意边界条件def binary_search(arr, target): left, right 0, len(arr) while left right: mid (left right) // 2 if arr[mid] target: left mid 1 else: right mid return left4. 完整解决方案将上述步骤组合起来import bisect class Solution: def numSmallerByFrequency(self, queries, words): def get_freq(word): if not word: return 0 min_char min(word) return word.count(min_char) freqs sorted([get_freq(word) for word in words]) res [] for q in queries: f_q get_freq(q) cnt len(freqs) - bisect.bisect_right(freqs, f_q) res.append(cnt) return res5. 复杂度分析时间复杂度预处理阶段O(n log n) 排序查询阶段每个查询O(log n)总体O(n log n m log n)其中n是words长度m是queries长度空间复杂度O(n) 存储预处理结果6. 常见错误与优化6.1 常见错误忘记处理空字符串情况二分查找边界条件处理不当没有对预处理数组排序就直接使用二分查找混淆bisect_left和bisect_right的使用场景6.2 优化建议对于大规模数据可以考虑并行预处理如果查询次数非常多可以考虑更高级的数据结构在实际工程中可以加入缓存机制7. 实际应用场景这种预处理二分查找的模式在很多实际场景中都有应用电商平台的价格过滤日志系统的错误级别统计用户画像的年龄分布查询时间序列数据的快速查询我在实际项目中就曾用类似的方法优化过一个用户行为分析系统将查询响应时间从秒级降到了毫秒级。关键在于预处理阶段要充分考虑后续查询的各种可能情况。