What is the optimal way to solve Range Frequency Queries?

The optimal approach uses a combination of preprocessing with hash maps or segment trees to answer queries in O(log n) time after O(n log n) preprocessing.

Why does brute force fail for this problem?

Brute force scanning leads to time-limit exceeded errors, as it takes too long to process large arrays and multiple queries.

How can segment trees be used to improve this problem?

Segment trees allow for efficient range queries by storing frequency counts for each segment of the array, reducing query time to O(log n).

What is the trade-off between using a hash map and a segment tree?

A hash map offers simpler implementation with preprocessing time O(n), but a segment tree offers better performance in handling range queries with O(log n) query time.

Can this problem be solved with just a frequency array?

Yes, a frequency array can be used for smaller cases where the array is static and the queries involve the entire array, but more advanced methods are needed for efficient handling of arbitrary subarrays.

#2080

Medium

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

区间内查询数字的频率

请你设计一个数据结构，它能求出给定子数组内一个给定值的频率。子数组中一个值的频率指的是这个子数组中这个值的出现次数。请你实现 RangeFreqQuery 类： RangeFreqQuery(int[] arr) 用下标从 0 开始的整数数组 arr 构造一个类的实例。 int quer…

数组哈希表二分查找设计线段树

题目描述

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

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

请你实现 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 <= 10⁵
1 <= arr[i], value <= 10⁴
0 <= left <= right < arr.length
调用 query 不超过 10⁵ 次。

lightbulb

解题思路

方法一：哈希表 + 二分查找

我们用一个哈希表 $g$ 来存储每个值对应的下标数组。在构造函数中，我们遍历数组 $\textit{arr}$ ，将每个值对应的下标加入到哈希表中。

在查询函数中，我们首先判断哈希表中是否存在给定的值。如果不存在，说明该值在数组中不存在，直接返回 $0$ 。否则，我们获取该值对应的下标数组 $\textit{idx}$ 。然后我们使用二分查找找到下标数组中第一个大于等于 $\textit{left}$ 的下标 $l$ ，以及第一个大于 $\textit{right}$ 的下标 $r$ 。最后返回 $r - l$ 即可。

时间复杂度方面，构造函数的时间复杂度为 $O(n)$ ，查询函数的时间复杂度为 $O(\log n)$ 。其中 $n$ 为数组的长度。空间复杂度为 $O(n)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

class RangeFreqQuery:

    def __init__(self, arr: List[int]):
        self.g = defaultdict(list)
        for i, x in enumerate(arr):
            self.g[x].append(i)

    def query(self, left: int, right: int, value: int) -> int:
        idx = self.g[value]
        l = bisect_left(idx, left)
        r = bisect_left(idx, right + 1)
        return r - l


# Your RangeFreqQuery object will be instantiated and called as such:
# obj = RangeFreqQuery(arr)
# param_1 = obj.query(left,right,value)

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
If the candidate suggests brute force, assess their awareness of time constraints and large input sizes.
question_mark
Look for familiarity with hash-based data structures and their use in optimizing range queries.
question_mark
Evaluate whether the candidate is comfortable with segment trees and understands their role in optimizing query performance.

warning

常见陷阱

外企场景

error
Using brute-force solutions without considering time limits will result in inefficiency for larger test cases.
error
Not handling edge cases, such as when the subarray has only one element or when the value isn't present at all.
error
Improper index management or off-by-one errors in calculating subarray boundaries.

swap_horiz

进阶变体

外企场景

arrow_right_alt
What if the query range is always the entire array? You could preprocess frequency counts for the entire array to quickly answer queries.
arrow_right_alt
What if the array is immutable and the query range doesn't change? A simple frequency map can be sufficient without advanced data structures.
arrow_right_alt
What if the queries involve different types of range queries, such as sum or maximum instead of frequency? The solution would need to be adjusted accordingly.

help

常见问题

外企场景

继续练习

#2424 最长上传前缀 #1157 子数组中占绝大多数的元素 #1146 快照数组