題目描述
我們來定義一個函數(shù) f(s)犬性，其中傳入?yún)?shù) s 是一個非空字符串；該函數(shù)的功能是統(tǒng)計 s 中（按字典序比較）最小字母的出現(xiàn)頻次腾仅。
例如乒裆，若 s = "dcce"，那么 f(s) = 2推励，因為最小的字母是 "c"鹤耍，它出現(xiàn)了 2 次。
現(xiàn)在验辞，給你兩個字符串數(shù)組待查表 queries 和詞匯表 words稿黄，請你返回一個整數(shù)數(shù)組 answer 作為答案，其中每個 answer[i] 是滿足 f(queries[i]) < f(W) 的詞的數(shù)目受神，W 是詞匯表 words 中的詞抛猖。
示例 1:
輸入：queries = ["cbd"], words = ["zaaaz"]
輸出：[1]
解釋：查詢 f("cbd") = 1，而 f("zaaaz") = 3 所以 f("cbd") < f("zaaaz")鼻听。
示例 2:
輸入：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] 都是小寫英文字母
解法
由題目可知撑碴，f 函數(shù)是指最小元素的出現(xiàn)頻次撑教，要返回的是 queries 數(shù)組中每個元素 queries[i] 對應的 W 的個數(shù)，W 是指 words 數(shù)組中的元素醉拓，其元素的 f 函數(shù)值大于對應的 queries[i] 的 f 函數(shù)值伟姐。
最簡單的方式自然是遍歷 queries 數(shù)組，對于每個元素遍歷 words 數(shù)組亿卤，計算出 W 的個數(shù)愤兵。不過該方式的時間開銷較大，不推薦該方式排吴。
因為每個元素的 f 函數(shù)值不大于 10秆乳，即值的范圍是有限的，因此不妨申請固定長度的數(shù)組，以 f 值對應數(shù)組下標屹堰，存儲每個 f 值對應的 W 元素的個數(shù)肛冶。因此只需要 queries 數(shù)組的一次遍歷，即可獲得要返回的結(jié)果扯键。
class Solution:
def numSmallerByFrequency(self, queries: List[str], words: List[str]) -> List[int]:
arr,count=[0]*11,0
for word in words:
arr[word.count(min(word))]+=1
for i in range(10,0,-1):
arr[i],count=count,count+arr[i]
return [arr[e.count(min(e))] for e in queries]
