比较字符串最小字母出现频次【LC1170】
定义一个函数 f(s)，统计 s 中**（按字典序比较）最小字母的出现频次** ，其中 s 是一个非空字符串。
例如，若 s = "dcce"，那么 f(s) = 2，因为字典序最小字母是 "c"，它出现了 2 次。
现在，给你两个字符串数组待查表 queries 和词汇表 words 。对于每次查询 queries[i] ，需统计 words 中满足f(queries[i]) < f(W) 的 词的数目 ，W 表示词汇表 words 中的每个词。
请你返回一个整数数组 answer 作为答案，其中每个 answer[i] 是第 i 次查询的结果。
思路
设计f方法返回字符串的最小字母出现的个数，使用数组记录最小字母出现的个数为x的words个数，并使用前缀和数组sum进行记录小于等于x的words个数，那么对于最小词频个数为y的查询，其结果为sum[m−1]−sum[y]
实现
class Solution { public int[] numSmallerByFrequency(String[] queries, String[] words) { int[] count = new int[11]; int[] sum = new int[11]; int m = sum.length, n = queries.length; for (String word : words){ count[f(word)]++; } for (int i = 1; i < m; i++){ sum[i] = sum[i - 1] + count[i]; } int[] res = new int[n]; for (int i = 0; i < n; i++){ int val = f(queries[i]); res[i] = sum[m - 1] - sum[val]; } return res; } public int f(String s){ int[] count = new int[26]; for (char c : s.toCharArray()){ count[c - 'a']++; } for (int i = 0; i < 26; i++){ if (count[i] != 0){ return count[i]; } } return -1; } }
复杂度
- 时间复杂度：O((n+m)p)，n和m为数组长度，p为数组中最长的字符串穿度
- 空间复杂度：O(C)
- 优化
- 使用后缀和代替前缀和
f方法不使用哈希表统计，我们只需要统计一个最小字符出现的数目，因此可以先假设是最大字符，然后遍历字符串进行比较，遇到更小的字符时更新字符重置出现次数【好久没用都忘了】
class Solution { public int[] numSmallerByFrequency(String[] queries, String[] words) { int[] count = new int[12]; for (String s : words) { count[f(s)]++; } for (int i = 9; i >= 1; i--) { count[i] += count[i + 1]; } int[] res = new int[queries.length]; for (int i = 0; i < queries.length; i++) { String s = queries[i]; res[i] = count[f(s) + 1]; } return res; } public int f(String s) { int cnt = 0; char ch = 'z'; for (int i = 0; i < s.length(); i++) { char c = s.charAt(i); if (c < ch) { ch = c; cnt = 1; } else if (c == ch) { cnt++; } } return cnt; } } 作者：力扣官方题解 链接：https://leetcode.cn/problems/compare-strings-by-frequency-of-the-smallest-character/solutions/2297291/bi-jiao-zi-fu-chuan-zui-xiao-zi-mu-chu-x-pb50/ 来源：力扣（LeetCode） 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
