题目

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

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

请你实现 RangeFreqQuery 类：

  • RangeFreqQuery(int[] arr) 用下标从 0 开始的整数数组 arr 构造一个类的实例。
  • int query(int left, int right, int value) 返回子数组 arr[left...right] 中 value 的频率。

示例 1

输入：

1
2
["RangeFreqQuery", "query", "query"]
[[[12, 33, 4, 56, 22, 2, 34, 33, 22, 12, 34, 56]], [1, 2, 4], [0, 11, 33]]

输出：

1
[null, 1, 2]

解释：

1
2
3
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. 直接遍历
  2. 增加缓存
  3. 使用哈希表存储每个数字的位置（本解法）

关键点：二分

bisect_left(a, x)：

在有序序列 a 中查找 x
返回第一个大于等于 x 的元素位置
如果所有元素都小于 x，返回 len(a)

bisect_right(a, x)：

在有序序列 a 中查找 x
返回第一个大于 x 的元素位置
如果所有元素都小于等于 x，返回 len(a)

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
from bisect import bisect_left, bisect_right
from collections import defaultdict
from typing import List


class RangeFreqQuery:
    def __init__(self, arr: List[int]):
        self.list_dict = defaultdict(list)
        for i, num in enumerate(arr):
            self.list_dict[num].append(i)

    def query(self, left: int, right: int, value: int) -> int:
        if value not in self.list_dict:
            return 0

        value_list = self.list_dict[value]
        left_pos = bisect_left(value_list, left)
        right_pos = bisect_right(value_list, right)

        return right_pos - left_pos