微网站开发项目合作协议,秦皇岛最新封闭通知,企业做网站设计,答题做任务网站题目描述#xff1a;
请你设计一个数据结构#xff0c;它能求出给定子数组内一个给定值的 频率 。
子数组中一个值的 频率 指的是这个子数组中这个值的出现次数。
请你实现 RangeFreqQuery 类#xff1a;
RangeFreqQuery(int[] arr) 用下标从 0 开始的整数数组 arr 构造…
题目描述
请你设计一个数据结构它能求出给定子数组内一个给定值的 频率 。
子数组中一个值的 频率 指的是这个子数组中这个值的出现次数。
请你实现 RangeFreqQuery 类
RangeFreqQuery(int[] arr) 用下标从 0 开始的整数数组 arr 构造一个类的实例。int query(int left, int right, int value) 返回子数组 arr[left...right] 中 value 的 频率 。
一个 子数组 指的是数组中一段连续的元素。arr[left...right] 指的是 nums 中包含下标 left 和 right 在内 的中间一段连续元素。 代码思路
类初始化 __init__ 方法
输入参数接收一个整数列表 arr。数据结构使用 defaultdict(list) 来存储每个值在数组 arr 中出现的所有索引。defaultdict 是 Python collections 模块中的一个容器它允许我们通过默认工厂函数这里是 list来自动初始化缺失的键。填充字典遍历数组 arr对于每个元素 v 和其索引 i将索引 i 添加到字典 dct 中键 v 对应的列表中。这样dct[value] 将会是一个列表包含所有值为 value 的元素的索引。
查询方法 query
输入参数接收三个整数 left、right 和 value分别表示查询的左边界、右边界和要查询的值。查询逻辑 使用 bisect.bisect_left 函数在 dct[value] 列表中查找第一个大于或等于 left 的索引的位置。这个位置之前的所有索引都不在查询区间 [left, right] 内。使用 bisect.bisect_right 函数在 dct[value] 列表中查找第一个大于 right 的索引的位置。这个位置之前的所有索引不包括这个位置本身都在查询区间 [left, right] 内。计算这两个位置之间的差值即 bisect_right 返回的位置减去 bisect_left 返回的位置。这个差值就是值 value 在区间 [left, right] 内出现的次数。
代码实现
class RangeFreqQuery:def __init__(self, arr: List[int]):self.dct defaultdict(list)for i, v in enumerate(arr): self.dct[v].append(i)def query(self, left: int, right: int, value: int) - int:return bisect.bisect_right(self.dct[value], right) - bisect.bisect_left(self.dct[value], left)
