当前位置：首页 > article >正文

【二分查找】

article 2024/12/5 0:51:07

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

解法1:

class Solution:
    def f(self, s: str) -> int:
        cnt = 0
        ch = 'z'
        for c in s:
            if c < ch:
                ch = c
                cnt = 1
            elif c == ch:
                cnt += 1
        return cnt

    def numSmallerByFrequency(self, queries: List[str], words: List[str]) -> List[int]:
        count = [0] * 12
        for s in words:
            count[self.f(s)] += 1
        for 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为1
        for c in s:
            if c < ch:     # 当前字符c，小于ch
                ch = c     # 更新ch
                cnt = 1    # 更新计数器
            elif c == ch:
                cnt += 1
        return cnt
    
    def lowerbound(self, nums, target):
        left = 0
        right = len(nums)-1  # 闭区间
        while left <= right:
            mid = left + (right - left) // 2
            if nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1
        return left

    def 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，看每个querie
        count_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) - x
            res.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 中字符串的最小字母出现频次，虽然相比第二种方法占用空间有所减少，但还是比第一种方法占用了更多空间。