交友网站建设要多少钱百度代运营公司

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

问题描述

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

输入描述

1. RangeFreqQuery(int[] arr)：构造函数，接受一个整数数组 arr。
2. 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 Listclass RangeFreqQuery:def __init__(self, arr: List[int]):# 创建一个哈希表，存储每个元素的位置pos = defaultdict(list)for i, x in enumerate(arr):pos[x].append(i)self.pos = posdef query(self, left: int, right: int, value: int) -> int:# 获取指定值的所有位置列表a = self.pos[value]# 使用二分查找查找区间内的出现次数return bisect_right(a, right) - bisect_left(a, left)

代码解析

1. 构造函数 __init__：

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

2. 查询函数 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)，因为我们使用了二分查找来确定区间的边界。

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

总结

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