【每日一题】Leetcode 2080. 区间内查询数字的频率

【每日一题】Leetcode 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 <= 105
1 <= arr[i], value <= 104
0 <= left <= right < arr.length
调用 query 不超过 10^5 次。

思路 1：（废案 超时 引出思路2）

1. 频率 = 出现次数 / len([arr[left : right + 1]])
2. 对 arr[left : right + 1] 排序，使用 Leetcode 1287 中的方法计算元素出现次数，即使用 bisect_left 和 bisect_right 分别确定有序列表中元素出现的 左索引 和 右索引，相减得到元素出现次数（时间复杂度\(O(log(n))\)）

思路 2：（哈希表 + 二分查找，时间复杂度（\(O(n+qlog(n))\)，q为查询次数））

1. 根据废案思路，每次查询时都需要对 [arr[left : right + 1]] 列表进行排序和查询，所以仅将“查询”操作放在 query 中；
2. 已知 left 和 right，则统计下标 left 到下标 right 之间 value 出现次数，所以出现的 value 的下标一定会在 left 和 right 之间。
3. 那么可以统计 value 的所有下标，设为 idx_list 列表，并使用 bisect_left 查找 left 插入位置 idx_left（第一个大于 left 的下标位置），以及 bisect_right 查找 right 插入位置 idx_right（第一个小于 right 的下标位置 + 1）
4. 那么 idx_right - idx_left = (value 出现次数)；
5. 所以可以创建一个哈希表，在初始化时统计各个元素的下标（由于是循环遍历，所以每个元素的下标列表是有序的），然后再在 query 中进行查找 left 和 right，之后计算差值得到 value 出现次数（频率）。

代码 2：（哈希表 + 二分查找，时间复杂度（\(O(n+qlog(n))\)，q为查询次数））

class RangeFreqQuery:

    def __init__(self, arr: List[int]):
        self.arr = arr
        self.docu = {}
        self.num_idx()

    def num_idx(self):
        for idx in range(len(self.arr)):
            item = self.arr[idx]
            if item not in self.docu:
                self.docu[item] = [idx]
            else:
                self.docu[item].append(idx)

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

        idx_list = self.docu[value]

        idx_left = bisect.bisect_left(idx_list, left)
        idx_right = bisect.bisect_right(idx_list, right)

        return idx_right - idx_left

感谢浏览，欢迎关注祁彧w博客！