比较字符串最小字母出现频次【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;}
  }
  

  • 复杂度
    • 时间复杂度：$\mathcal{O}((n+m)p)$，n和m为数组长度，p为数组中最长的字符串穿度
    • 空间复杂度：$\mathcal{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）
  著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。