LeetCode 1170. 比较字符串最小字母出现频次

Categories:

题目描述
思路分析
1. 解法一：统计最小字符频次 + 二分（推荐）
相似题目

题目描述

✅ 1170. 比较字符串最小字母出现频次

思路分析

解法一：统计最小字符频次 + 二分（推荐）

核心思路：

定义 f(s) 为字符串中最小字母的出现次数。

先计算 words 的 f 值并排序。

对每个 query 计算 f(query)，用二分找出 words 中 f > f(query) 的数量。

复杂度分析：

时间复杂度：O((m + n) log n + L)，其中 n 为 words 数量，m 为 queries 数量，L 为总字符串长度。

空间复杂度：O(n)，存储 words 的频次数组。

import java.util.Arrays;

class Solution {
    public int[] numSmallerByFrequency(String[] queries, String[] words) {
        int[] freqWords = new int[words.length];
        for (int i = 0; i < words.length; i++) {
            freqWords[i] = minCharFreq(words[i]);
        }
        Arrays.sort(freqWords);

        int[] res = new int[queries.length];
        for (int i = 0; i < queries.length; i++) {
            int q = minCharFreq(queries[i]);
            int idx = upperBound(freqWords, q);
            res[i] = freqWords.length - idx;
        }
        return res;
    }

    private int minCharFreq(String s) {
        char min = 'z';
        int count = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c < min) {
                min = c;
                count = 1;
            } else if (c == min) {
                count++;
            }
        }
        return count;
    }

    private int upperBound(int[] arr, int target) {
        int left = 0;
        int right = arr.length;
        while (left < right) {
            int mid = left + (right - left) / 2;
            if (arr[mid] <= target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }
}

import "sort"

func numSmallerByFrequency(queries []string, words []string) []int {
    freqWords := make([]int, len(words))
    for i, w := range words {
        freqWords[i] = minCharFreq(w)
    }
    sort.Ints(freqWords)

    res := make([]int, len(queries))
    for i, q := range queries {
        fq := minCharFreq(q)
        idx := sort.Search(len(freqWords), func(i int) bool {
            return freqWords[i] > fq
        })
        res[i] = len(freqWords) - idx
    }
    return res
}

func minCharFreq(s string) int {
    min := byte('z')
    count := 0
    for i := 0; i < len(s); i++ {
        c := s[i]
        if c < min {
            min = c
            count = 1
        } else if c == min {
            count++
        }
    }
    return count
}

相似题目

题目	难度	考察点
242. 有效的字母异位词	简单	频次统计
451. 根据字符出现频率排序	中等	频次统计
692. 前K个高频单词	中等	频次统计
387. 字符串中的第一个唯一字符	简单	频次统计
1189. “气球” 的最大数量	简单	频次统计

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2023/95771235