| 题目链接 | 1170. 比较字符串最小字母出现频次 |
|---|---|
| 思路 | 题意不易理解；排序+二分（upper_bound） |
| 题解链接 | Python简洁解法 |
| 关键点 | 预先处理words |
| 时间复杂度 | \(O((n+m)p)\) |
| 空间复杂度 | \(O(1)\) |
代码实现：
class Solution:
def numSmallerByFrequency(self, queries: List[str], words: List[str]) -> List[int]:
nums = sorted(
s.count(min(s)) for s in words
)
n = len(nums)
def upper_bound(val):
left, right = -1, n
while left+1<right:
mid = (left+right) // 2
if nums[mid] > val:
right = mid
else:
left = mid
return right
return [
n-upper_bound(q.count(min(q))) for q in queries
]
Python-官方库
class Solution:
def numSmallerByFrequency(self, queries: List[str], words: List[str]) -> List[int]:
nums = sorted(
s.count(min(s)) for s in words
)
n = len(nums)
return [
n-bisect_right(nums, q.count(min(q))) for q in queries
]