LeetCode2080.区间内查询数字的频率：哈希表+二分查找

【LetMeFly】2080.区间内查询数字的频率：哈希表+二分查找

力扣题目链接： leetcode /problems/range-frequency-queries/

请你设计一个数据结构，它能求出给定子数组内一个给定值的 频率 。

子数组中一个值的 频率 指的是这个子数组中这个值的出现次数。

请你实现 RangeFreqQuery 类：

RangeFreqQuery(int[] arr) 用下标从 0 开始的整数数组 arr 构造一个类的实例。int query(int left, int right, int value) 返回子数组 arr[left...right] 中 value 的 频率 。

一个 子数组 指的是数组中一段连续的元素。arr[left...right] 指的是 nums 中包含下标 left 和 right 在内 的中间一段连续元素。

 

示例 1：

输入： ["RangeFreqQuery", "query", "query"] [[[12, 33, 4, 56, 22, 2, 34, 33, 22, 12, 34, 56]], [1, 2, 4], [0, 11, 33]] 输出： [null, 1, 2] 解释： RangeFreqQuery rangeFreqQuery = new RangeFreqQuery([12, 33, 4, 56, 22, 2, 34, 33, 22, 12, 34, 56]); rangeFreqQuery.query(1, 2, 4); // 返回 1 。4 在子数组 [33, 4] 中出现 1 次。 rangeFreqQuery.query(0, 11, 33); // 返回 2 。33 在整个子数组中出现 2 次。

 

提示：

1 <= arr.length <= 1051 <= arr[i], value <= 1040 <= left <= right < arr.length调用 query 不超过 105 次。 解题方法：哈希表+二分查找

遍历数组，将value出现的所有下标放到哈希表ma[value]这个数组中。这样，只需要查询ma[value]就能得到value的所有出现位置下标的递增数组。

接着二分查找这个数组，就能确定在[left, right]范围内的下标有几个了。

时间复杂度：初始化 O ( n ) O(n) O(n)，单次查询 O ( log ⁡ n ) O(\log n) O(logn)。其中 n = l e n ( a r r ) n=len(arr) n=len(arr)空间复杂度 O ( n ) O(n) O(n) AC代码 C++ /* * @Author: LetMeFly * @Date: 2025-02-18 10:08:36 * @LastEditors: LetMeFly.xyz * @LastEditTime: 2025-02-18 10:15:30 */ class RangeFreqQuery { private: unordered_map<int, vector<int>> ma; public: RangeFreqQuery(vector<int>& arr) { for (int i = 0; i < arr.size(); i++) { ma[arr[i]].push_back(i); } } int query(int left, int right, int value) { unordered_map<int, vector<int>>::iterator it = ma.find(value); if (it == ma.end()) { return 0; } vector<int>& v = it->second; // 这里必须引用否则会超时 return upper_bound(v.begin(), v.end(), right) - lower_bound(v.begin(), v.end(), left); } }; /** * Your RangeFreqQuery object will be instantiated and called as such: * RangeFreqQuery* obj = new RangeFreqQuery(arr); * int param_1 = obj->query(left,right,value); */ Python ''' Author: LetMeFly Date: 2025-02-18 10:17:02 LastEditors: LetMeFly.xyz LastEditTime: 2025-02-18 10:36:00 ''' from typing import List from collections import defaultdict from bisect import bisect_left, bisect_right class RangeFreqQuery: def __init__(self, arr: List[int]): self.ma = defaultdict(list) for i, v in enumerate(arr): self.ma[v].append(i) def query(self, left: int, right: int, value: int) -> int: if value not in self.ma: return 0 v = self.ma[value] return bisect_right(v, right) - bisect_left(v, left) # Your RangeFreqQuery object will be instantiated and called as such: # obj = RangeFreqQuery(arr) # param_1 = obj.query(left,right,value) Go /* * @Author: LetMeFly * @Date: 2025-02-18 10:17:10 * @LastEditors: LetMeFly.xyz * @LastEditTime: 2025-02-18 10:50:44 */ package main import "sort" type RangeFreqQuery map[int][]int func Constructor(arr []int) RangeFreqQuery { ma := map[int][]int{} for i, v := range arr { ma[v] = append(ma[v], i) } return ma } func (this *RangeFreqQuery) Query(left int, right int, value int) int { v := (*this)[value] return sort.SearchInts(v, right + 1) - sort.SearchInts(v, left) } /** * Your RangeFreqQuery object will be instantiated and called as such: * obj := Constructor(arr); * param_1 := obj.Query(left,right,value); */

同步发文于CSDN和我的个人博客，原创不易，转载经作者同意后请附上原文链接哦~

千篇源码题解已开源

Tisfy： blog.letmefly.xyz/2025/02/18/LeetCode 2080.区间内查询数字的频率/