解决“区间内查询数字的频率”问题

解决“区间内查询数字的频率”问题 问题描述

我们需要设计一个数据结构 RangeFreqQuery，它能有效地查询给定子数组内一个特定值的频率。具体来说，要求实现一个 query 方法，用于返回子数组 arr[left...right] 中某个给定值出现的次数。

输入描述 RangeFreqQuery(int[] arr)：构造函数，接受一个整数数组 arr。query(int left, int right, int value)：查询方法，返回子数组 arr[left...right] 中 value 出现的频率。 输出描述

对于每次 query 操作，返回一个整数，表示指定区间内特定值的出现次数。

解题思路 1. 使用哈希表记录元素位置

首先，我们可以使用一个哈希表 pos 来存储数组中每个元素的所有位置。对于数组中的每个元素，我们遍历一遍数组，将它们的位置记录在 pos 中。这样，我们能够快速查询一个元素在整个数组中的所有索引。

2. 使用二分查找提高查询效率

当我们需要查询某个值在区间 [left, right] 内出现的次数时，直接遍历区间的时间复杂度会很高。为了提高查询效率，我们可以利用二分查找算法：

使用 bisect_left 查找 value 第一次出现的位置（即第一个大于等于 left 的位置）。使用 bisect_right 查找 value 最后一次出现的位置（即第一个大于 right 的位置）。

通过这两个二分查找操作，我们可以快速得出该值在区间内的频率，时间复杂度为 O(log n)。

3. 总体时间复杂度 初始化：遍历一次数组并记录元素的位置，时间复杂度为 O(n)。查询：每次查询都进行两次二分查找，时间复杂度为 O(log n)。

因此，整个数据结构的操作非常高效，能够满足大规模数据的查询需求。

代码实现 from collections import defaultdict from bisect import bisect_left, bisect_right from typing import List class RangeFreqQuery: def __init__(self, arr: List[int]): # 创建一个哈希表，存储每个元素的位置 pos = defaultdict(list) for i, x in enumerate(arr): pos[x].append(i) self.pos = pos def query(self, left: int, right: int, value: int) -> int: # 获取指定值的所有位置列表 a = self.pos[value] # 使用二分查找查找区间内的出现次数 return bisect_right(a, right) - bisect_left(a, left) 代码解析

构造函数 __init__：

我们通过遍历数组 arr，将每个值的位置存储在哈希表 pos 中，pos[x] 存储的是值 x 在数组中的所有出现位置。

查询函数 query：

对于给定的查询区间 [left, right] 和查询值 value，首先获取该值在数组中的所有位置 a。使用 bisect_left(a, left) 查找位置 left 对应的最小索引（即第一个不小于 left 的位置）。使用 bisect_right(a, right) 查找位置 right 对应的最大索引（即第一个大于 right 的位置）。通过 bisect_right(a, right) - bisect_left(a, left) 计算出 value 在区间 [left, right] 中的出现次数。 示例 示例 1 # 创建 RangeFreqQuery 实例 rangeFreqQuery = RangeFreqQuery([12, 33, 4, 56, 22, 2, 34, 33, 22, 12, 34, 56]) # 查询 4 在子数组 [1, 2] 中的出现次数 print(rangeFreqQuery.query(1, 2, 4)) # 输出: 1 # 查询 33 在子数组 [0, 11] 中的出现次数 print(rangeFreqQuery.query(0, 11, 33)) # 输出: 2 解释 第一个查询：4 在子数组 [33, 4] 中出现了 1 次。第二个查询：33 在整个数组 [12, 33, 4, 56, 22, 2, 34, 33, 22, 12, 34, 56] 中出现了 2 次。 时间复杂度分析 初始化时，构造哈希表的时间复杂度是 O(n)，其中 n 是数组的长度。每次查询的时间复杂度是 O(log n)，因为我们使用了二分查找来确定区间的边界。

因此，该方案非常高效，适合大规模数据的查询。

总结

通过使用哈希表和二分查找，我们能够在高效地查询给定值在指定区间的频率。在数组初始化时，先记录每个元素的索引，查询时利用二分查找快速定位元素在指定区间的位置，从而实现高效的查询。