leetcode在力扣 App 中打开
调试中...
调试中...
题目描述
题目描述
题解
题解
提交记录
提交记录
代码
代码
测试用例
测试用例
测试结果
测试结果
中等
相关标签
相关企业
提示

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

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

请你实现 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 <= 105
  • 1 <= arr[i], value <= 104
  • 0 <= left <= right < arr.length
  • 调用 query 不超过 105 次。
通过次数
30.4K
提交次数
70.6K
通过率
43.0%


相关企业

提示 1
The queries must be answered efficiently to avoid time limit exceeded verdict.

提示 2
Store the elements of the array in a data structure that helps answering the queries efficiently.

提示 3
Use a hash table that stored for each value, the indices where that value appeared.

提示 4
Use binary search over the indices of a value to find its range frequency.

评论 (0)

贡献者
© 2025 领扣网络(上海)有限公司
0 人在线
行 1,列 1
["RangeFreqQuery","query","query"]
[[[12,33,4,56,22,2,34,33,22,12,34,56]],[1,2,4],[0,11,33]]
Source