Medium

题目描述

定义函数 f(s) 为非空字符串 s 中字典序最小字符的出现频率。例如，如果 s = “dcce”，那么 f(s) = 2，因为字典序最小字符是 ‘c’，它出现了 2 次。

给你一个字符串数组 words 和另一个查询字符串数组 queries。对于每个查询 queries[i]，统计 words 中满足 f(queries[i]) < f(W) 的字符串 W 的数目。

返回一个整数数组 answer，其中 answer[i] 是第 i 个查询的答案。

示例 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(s) 函数的定义：找到字符串中字典序最小的字符，并返回其出现次数。

主要步骤：

  1. 实现 f 函数：遍历字符串，找到字典序最小的字符，然后统计该字符的出现次数。

  2. 预处理 words 数组：对每个 word 计算 f(word) 的值，存储在数组中并排序。排序后可以使用二分查找快速统计满足条件的个数。

  3. 处理查询：对于每个查询字符串，计算 f(query)，然后在排序后的数组中二分查找有多少个值大于 f(query)。

优化思路：

  • 使用二分查找而不是线性扫描，可以将每个查询的时间复杂度从 O(n) 降低到 O(log n)
  • 预处理一次排序，避免每次查询都重新计算

推荐解法：预处理 + 二分查找，时间效率最优。

代码实现

class Solution {
public:
    int f(const string& s) {
        char minChar = 'z';
        for (char c : s) {
            minChar = min(minChar, c);
        }
        int count = 0;
        for (char c : s) {
            if (c == minChar) count++;
        }
        return count;
    }
    
    vector<int> numSmallerByFrequency(vector<string>& queries, vector<string>& words) {
        vector<int> wordFreqs;
        for (const string& word : words) {
            wordFreqs.push_back(f(word));
        }
        sort(wordFreqs.begin(), wordFreqs.end());
        
        vector<int> result;
        for (const string& query : queries) {
            int queryFreq = f(query);
            int count = wordFreqs.end() - upper_bound(wordFreqs.begin(), wordFreqs.end(), queryFreq);
            result.push_back(count);
        }
        
        return result;
    }
};

class Solution:
    def f(self, s: str) -> int:
        min_char = min(s)
        return s.count(min_char)
    
    def numSmallerByFrequency(self, queries: List[str], words: List[str]) -> List[int]:
        import bisect
        
        word_freqs = [self.f(word) for word in words]
        word_freqs.sort()
        
        result = []
        for query in queries:
            query_freq = self.f(query)
            # 找到第一个大于 query_freq 的位置
            pos = bisect.bisect_right(word_freqs, query_freq)
            # 大于 query_freq 的元素个数
            count = len(word_freqs) - pos
            result.append(count)
        
        return result

public class Solution {
    private int F(string s) {
        char minChar = s.Min();
        return s.Count(c => c == minChar);
    }
    
    public int[] NumSmallerByFrequency(string[] queries, string[] words) {
        int[] wordFreqs = new int[words.Length];
        for (int i = 0; i < words.Length; i++) {
            wordFreqs[i] = F(words[i]);
        }
        Array.Sort(wordFreqs);
        
        int[] result = new int[queries.Length];
        for (int i = 0; i < queries.Length; i++) {
            int queryFreq = F(queries[i]);
            int pos = Array.BinarySearch(wordFreqs, queryFreq + 1);
            if (pos < 0) {
                pos = ~pos;
            }
            result[i] = wordFreqs.Length - pos;
        }
        
        return result;
    }
}

var numSmallerByFrequency = function(queries, words) {
    const f = (s) => {
        const minChar = s.split('').sort()[0];
        return s.split('').filter(c => c === minChar).length;
    };
    
    const wordFreqs = words.map(f);
    
    return queries.map(query => {
        const queryFreq = f(query);
        return wordFreqs.filter(freq => queryFreq < freq).length;
    });
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O((m + n) × k + m log m + n log m)其中 m 是 words 长度，n 是 queries 长度，k 是字符串平均长度。计算 f 函数需要 O(k)，排序需要 O(m log m)，每次二分查找需要 O(log m)
空间复杂度O(m)存储 words 的频率数组