1170.比较字符串最小字母出现频次

链接：1170.比较字符串最小字母出现频次
难度：Medium
标签：数组、哈希表、字符串、二分查找、排序
简介：定义一个函数 f(s)，统计 s 中（按字典序比较）最小字母的出现频次 ，其中 s 是一个非空字符串。请你返回一个整数数组 answer 作为答案，其中每个 answer[i] 是第 i 次查询的结果。

题解 1 - cpp

• 编辑时间：2023-06-10
• 执行用时：8ms
• 内存消耗：11.4MB
• 编程语言：cpp
• 解法介绍：排序后二分查找。

class Solution {
public:
    vector<int> numSmallerByFrequency(vector<string>& queries, vector<string>& words) {
        vector<int> ws;
        for (auto &w : words) ws.push_back(f(w));
        sort(ws.begin(), ws.end());
        vector<int> res;
        for (auto &q : queries) {
            int target = f(q), l = 0, r = words.size();
            while (l < r) {
                int m = (l + r) / 2;
                if (target < ws[m]) r = m;
                else l = m + 1;
            }
            res.push_back(words.size() - l);
        }
        return res;
    }
    int f(string &w) {
        int cnt = 0;
        char ch = 'z';
        for (auto &c : w) {
            if (c < ch) ch = c, cnt = 1;
            else if (c == ch) cnt++;
        }
        return cnt;
    }
};

题解 2 - python

• 编辑时间：2023-06-10
• 执行用时：56ms
• 内存消耗：16.7MB
• 编程语言：python
• 解法介绍：同上。

class Solution:
    def numSmallerByFrequency(self, queries: List[str], words: List[str]) -> List[int]:
        def f(w: str):
            cnt = 0
            ch = ord('z')
            for c in w:
                if ord(c) < ch:
                    ch = ord(c)
                    cnt = 1
                elif ord(c) == ch:
                    cnt += 1
            return cnt
        ws = [f(w) for w in words]
        ws.sort()
        def query(q: str):
            target = f(q)
            l = 0
            r = len(words)
            while l < r:
                m = (l + r)//2
                if target < ws[m]:
                    r = m
                else:
                    l = m + 1
            return len(words) - l
        return [query(q) for q in queries]