武汉网站建设模板怎么制作_公司的网址_石家庄seo管理_介绍产品的营销推文

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

解法1:

class Solution:def f(self, s: str) -> int:cnt = 0ch = 'z'for c in s:if c < ch:ch = ccnt = 1elif c == ch:cnt += 1return cntdef numSmallerByFrequency(self, queries: List[str], words: List[str]) -> List[int]:count = [0] * 12for s in words:count[self.f(s)] += 1for i in range(9, 0, -1):count[i] += count[i + 1]res = []for s in queries:res.append(count[self.f(s) + 1])return res作者：力扣官方题解
链接：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）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

解法2：排序+查找

class Solution:def f(self, s: str):# 如何实现f？统计最小字母的出现频次！cnt = 0   # 最小字母出现次数ch = 'z'  # 初始化当前的最小字母# 遍历s所有字符c，只要出现更小的就更新cnt为1for c in s:if c < ch:     # 当前字符c，小于chch = c     # 更新chcnt = 1    # 更新计数器elif c == ch:cnt += 1return cntdef lowerbound(self, nums, target):left = 0right = len(nums)-1  # 闭区间while left <= right:mid = left + (right - left) // 2if nums[mid] < target:left = mid + 1else:right = mid - 1return leftdef numSmallerByFrequency(self, queries: List[str], words: List[str]) -> List[int]:# 对于每个queries[i],统计words中有多少个word满足 f(queries[i]) < f(word) , f(xxx)是最小字母出现次数# 已知所有字符长度最长10# 用一个count[]res = []# 计算所有f(word),存到对应位置count_words = [0] * len(words) for i in range(len(words)):   # self.f(s)可以计算words中每个word的最小字母出现频率count_words[i] = self.f(words[i]) # 接下来比对所有querie，看每个queriecount_words.sort()queries_words = [0] * len(queries)for i in range(len(queries)):   # self.f(s)可以计算words中每个word的最小字母出现频率queries_words[i] = self.f(queries[i]) x = self.lowerbound(count_words, queries_words[i]+1)x = len(count_words) - xres.append(x)return res

解法3：

class Solution:def numSmallerByFrequency(self, queries: List[str], words: List[str]) -> List[int]:a = sorted(s.count(min(s)) for s in words)return [len(a) - bisect_right(a, q.count(min(q))) for q in queries]

以下是对这三种方法思路、异同以及核心思路的详细解释：

一、整体问题分析

题目要求对于给定的两个字符串数组 queries 和 words，定义函数 f(s) 来统计字符串 s 中字典序最小字母的出现频次，然后针对每个 queries[i]，统计 words 中满足 f(queries[i]) < f(word) 的词的数目。

二、三种方法详解

1. 第一种方法（官方题解）

• 核心思路：
  • 首先实现函数 f(s)，通过遍历字符串 s，不断更新当前遇到的字典序最小字母 ch 以及它的出现频次 cnt。
  • 然后提前计算出所有 words 中字符串的 f(s) 值，并使用一个长度固定为 12 的整数数组 count（因为 f(s) 的范围是 [1, 10]）来统计每种 f(words[i]) 的个数。
  • 为了加快后续查询答案的计算速度，通过倒序遍历 count 数组，将其更新为后缀和数组。这样，对于每个 queries[i]，对应的答案就是 count[f(queries[i]) + 1]。
• 具体步骤：
  • 在 f(self, s: str) -> int 函数中：
    • 初始化 cnt = 0 表示最小字母出现次数，ch = 'z' 作为当前遇到的字典序最小的字母。
    • 遍历字符串 s 中的每个字符 c：
      • 如果 c < ch，说明遇到了更小的字典序字母，更新 ch 为 c，并将 cnt 重置为 1。
      • 如果 c == ch，说明是当前最小字母再次出现，将 cnt 加 1。
    • 最后返回 cnt，即为字符串 s 中字典序最小字母的出现频次。
  • 在 numSmallerByFrequency 函数中：
    • 初始化 count = [0] * 12，用于统计每种 f(words[i]) 的个数。
    • 遍历 words 数组，通过 count[self.f(s)] += 1 计算每个 words[i] 的 f(s) 值并在 count 数组中相应位置累加计数。
    • 通过倒序遍历 count 数组，将其更新为后缀和数组，即 for i in range(9, 0, -1): count[i] += count[i + 1];。
    • 最后遍历 queries 数组，对于每个 queries[i]，通过 res.append(count[self.f(s) + 1]) 计算满足条件的 words 中字符串的个数并添加到结果数组 res 中。

2. 第二种方法（你的解法）

• 核心思路：
  • 同样先实现函数 f(s) 来计算字符串中字典序最小字母的出现频次。
  • 然后分别计算出 words 数组中每个字符串的 f(s) 值存到 count_words 数组，以及 queries 数组中每个字符串的 f(s) 值存到 queries_words 数组。
  • 对 count_words 数组进行排序，再针对每个 queries_words[i]，通过二分查找函数 lowerbound 在 count_words 数组中找到大于 queries_words[i] + 1 的最小索引 x，最后通过 len(count_words) - x 得到满足条件的 words 中字符串的个数并添加到结果数组 res 中。
• 具体步骤：
  • 在 f(self, s: str) 函数中，实现逻辑与第一种方法的 f(s) 函数基本相同，通过遍历字符串 s，更新最小字母及其出现频次，最后返回频次值。
  • 在 numSmallerByFrequency 函数中：
    • 初始化 count_words = [0] * len(words) 和 queries_words = [0] * len(queries) 两个数组。
    • 遍历 words 数组，通过 count_words[i] = self.f(words[i]) 计算每个 words[i] 的 f(s) 值并存入 count_words 数组。
    • 遍历 queries 数组，通过 queries_words[i] = self.f(queries[i]) 计算每个 queries[i] 的 f(s) 值并存入 queries_words 数组。
    • 对 count_words 数组进行排序。
    • 针对每个 queries_words[i]，通过 x = self.lowerbound(count_words, queries_words[i] + 1) 进行二分查找，找到大于 queries_words[i] + 1 的最小索引 x，再通过 x = len(count_words) - x 得到满足条件的个数并添加到结果数组 res 中。

3. 第三种方法

• 核心思路：
  • 利用了 sorted 函数和 bisect_right 函数的特性来简洁地解决问题。首先通过生成器表达式 sorted(s.count(min(s)) for s in words) 快速计算出 words 中每个字符串的最小字母出现频次并排序得到数组 a。
  • 然后对于每个 queries 中的字符串 q，通过 q.count(min(q)) 计算其最小字母出现频次，再利用 bisect_right 函数在排序后的数组 a 中找到大于该频次的最小索引，最后通过 len(a) - bisect_right(a, q.count(min(q))) 得到满足条件的 words 中字符串的个数并添加到结果数组中。
• 具体步骤：
  • 在 numSmallerByFrequency 函数中：
    • 通过 a = sorted(s.count(min(s)) for s in words) 计算并排序 words 中每个字符串的最小字母出现频次得到数组 a。
    • 遍历 queries 数组，对于每个 q：
      • 通过 q.count(min(q)) 计算 q 的最小字母出现频次。
      • 通过 bisect_right(a, q.count(min(q))) 在数组 a 中找到大于该频次的最小索引。
      • 通过 len(a) - bisect_right(a, q.count(min(q))) 得到满足条件的 words 中字符串的个数并添加到结果数组中。

三、三种方法的异同点

1. 相同点

• 都需要先实现一个计算字符串中字典序最小字母出现频次的函数 f(s)，且实现逻辑基本相似，都是通过遍历字符串，不断更新最小字母及其出现频次。删除线格式
• 最终目的都是针对每个 queries 中的字符串，统计 words 中满足 f(queries[i]) < f(word) 的词的数目，并返回一个结果数组。

2. 不同点

• 数据处理方式：
  • 第一种方法：使用一个固定长度的数组 count 来统计 words 中不同 f(s) 值的个数，并通过将其更新为后缀和数组来加速查询。这种方式利用了 f(s) 值范围有限的特点，通过巧妙的预处理和后缀和计算，能够快速得到每个 queries[i] 的结果。
  • 第二种方法：分别计算 words 和 queries 的 f(s) 值并存到两个数组 count_words 和 queries_words 中，然后对 count_words 进行排序，再通过二分查找来确定满足条件的个数。这种方法相对更直观，但需要额外的数组存储和排序、二分查找等操作。
  • 第三种方法：通过生成器表达式和 sorted 函数快速计算并排序 words 中字符串的最小字母出现频次得到数组 a，然后利用 bisect_right 函数在 a 中查找满足条件的索引，进而得到满足条件的个数。这种方法代码最为简洁，但需要对 bisect_right 函数的使用比较熟悉。
• 时间复杂度：
  • 第一种方法：时间复杂度为 $O((n+m)p)$，其中 $n$ 是 queries 的长度，$m$ 是 words 的长度，$p$ 是 queries 和 words 中的最长字符串的长度。主要时间消耗在计算 f(s) 值以及对 count 数组的预处理和查询上。
  • 第二种方法：时间复杂度也为 $O((n+m)p)$，同样主要消耗在计算 f(s) 值、数组排序（一般排序算法时间复杂度为 $O(m\log m)$，这里 $m$ 是 words 的长度）以及二分查找（每次二分查找时间复杂度为 $O(\log m)$，总共 $n$ 次查询，所以是 $O(n\log m)$）上。总体来说，在时间复杂度上与第一种方法相近，但由于排序和二分查找的操作，可能在实际运行中效率稍低一些。
  • 第三种方法：时间复杂度同样为 $O((n+m)p)$，主要消耗在计算 words 中字符串的最小字母出现频次（通过生成器表达式和 sorted 函数，时间复杂度与 words 的长度和字符串长度有关）以及对 queries 中的每个字符串进行查找（通过 bisect_right 函数，每次查找时间复杂度为 $O(\log m)$，总共 $n$ 次查询）上。虽然代码简洁，但在时间复杂度上与前两种方法基本处于同一量级。
• 空间复杂度：
  • 第一种方法：空间复杂度为 $O(1)$，不统计返回值所占用的空间，只使用了常数个变量，通过巧妙地利用一个固定长度的数组 count 来完成统计和查询，避免了大量额外的空间占用。
  • 第二种方法：空间复杂度为 $O(n+m)$，因为分别创建了长度为 n 的 queries_words 数组和长度为 m 的 count_words 数组来存储计算得到的 f(s) 值，相比第一种方法占用了更多的空间。
  • 第三种方法：空间复杂度为 $O(m)$，主要是因为通过 sorted 函数创建了一个长度为 m 的数组 a 来存储 words 中字符串的最小字母出现频次，虽然相比第二种方法占用空间有所减少，但还是比第一种方法占用了更多空间。

综上所述，三种方法都能解决问题，但在数据处理方式、时间复杂度和空间复杂度等方面存在差异，你可以根据具体的需求和应用场景选择合适的方法。