区间内查询数字的频率

2080. 区间内查询数字的频率

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

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

请你实现 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⁵ 次。

原站题解

去查看

上次编辑到这里，代码来自缓存点击恢复默认模板

class RangeFreqQuery { public: RangeFreqQuery(vector<int>& arr) { } int query(int left, int right, int value) { } }; /** * Your RangeFreqQuery object will be instantiated and called as such: * RangeFreqQuery* obj = new RangeFreqQuery(arr); * int param_1 = obj->query(left,right,value); */

golang 解法, 执行用时: 604 ms, 内存消耗: 80.6 MB, 提交时间: 2023-04-19 10:00:01

type RangeFreqQuery struct{ pos [1e4 + 1]sort.IntSlice }

func Constructor(arr []int) (q RangeFreqQuery) {
	for i, value := range arr {
		q.pos[value] = append(q.pos[value], i) // 统计 value 在 arr 中的所有下标位置
	}
	return
}

func (q *RangeFreqQuery) Query(left, right, value int) int {
	p := q.pos[value] // value 在 arr 中的所有下标位置
	return p[p.Search(left):].Search(right + 1) // 在下标位置上二分，求 [left,right] 之间的下标个数，即为 value 的频率
}


/**
 * Your RangeFreqQuery object will be instantiated and called as such:
 * obj := Constructor(arr);
 * param_1 := obj.Query(left,right,value);
 */

python3 解法, 执行用时: 604 ms, 内存消耗: 54.7 MB, 提交时间: 2023-04-19 09:59:30

class RangeFreqQuery:

    def __init__(self, arr: List[int]):
        # 数值为键，出现下标数组为值的哈希表
        self.occurence = defaultdict(list)
        # 顺序遍历数组初始化哈希表
        n = len(arr)
        for i in range(n):
            self.occurence[arr[i]].append(i)

    def query(self, left: int, right: int, value: int) -> int:
        # 查找对应的出现下标数组，不存在则为空
        pos = self.occurence[value]
        # 两次二分查找计算子数组内出现次数
        l = bisect_left(pos, left)
        r = bisect_right(pos, right)
        return r - l

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

上一题

下一题

详情