[LeetCode] 每日一题 2080. 区间内查询数字的频率

题目链接

https://leetcode.cn/problems/range-frequency-queries

题目描述

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

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

请你实现 RangeFreqQuery 类：

• RangeFreqQuery(int[] arr) 用下标从 0 开始的整数数组 arr 构造一个类的实例。

• int query(int left, int right, int value) 返回子数组 arr[left...right] 中 value 的 频率 。

一个 子数组 指的是数组中一段连续的元素。arr[left...right] 指的是 nums 中包含下标 left 和 right 在内 的中间一段连续元素。

示例输入

示例

输入：
["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^5

• 1 <= arr[i], value <= 10^4

• 0 <= left <= right < arr.length

• 调用 query 不超过 10^5 次。

解题思路

今天的题目要求我们设计一个数据结构，用于查询给定子数组内某个值的频率。为了高效地解决这个问题，我的思路是使用一个 Map 来存储数组中每个值的所有出现位置。具体来说，Map 的键是数组中的值，值是该值在数组中所有出现位置的索引列表

在查询时，我们通过对该列表进行二分查找来找到指定区间内该值的出现次数。具体而言，我们需要使用二分查找找到该值在给定区间 left 和 right 内的上下界，从而快速计算该值在这个区间内出现的次数。通过这种方式，我们能够大大提高查询效率

代码实现

class RangeFreqQuery {
    Map<Integer, List<Integer>> existMap = new HashMap<>();

    public RangeFreqQuery(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            existMap.putIfAbsent(arr[i], new ArrayList<>());
            existMap.get(arr[i]).add(i);
        }
    }

    public int query(int left, int right, int value) {
        List<Integer> exist = existMap.getOrDefault(value, null);
        if (exist == null) {
            return 0;
        }
        // left <= l <= r <= right
        int l = findBigger(exist, left);
        int r = findSmaller(exist, right);
        return r - l + 1;
    }

    private int findBigger(List<Integer> exist, int target) {
        int low = 0, high = exist.size() - 1;
        while (low <= high) {
            int mid = (low + high) / 2;
            if (exist.get(mid) < target) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return low;
    }

    private int findSmaller(List<Integer> exist, int target) {
        int low = 0, high = exist.size() - 1;
        while (low <= high) {
            int mid = (low + high) / 2;
            if (exist.get(mid) <= target) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return high;
    }
}

复杂度分析

• 时间复杂度：

  • RangeFreqQuery 的构造函数会遍历数组一次，因此时间复杂度为 O(n)，其中 n 是数组的长度

  • query 函数每次查询时，我们需要在 existMap 中查找值对应的索引列表，并对该列表执行两次二分查找。每次二分查找的时间复杂度是 O(log n)，因此查询操作的时间复杂度是 O(log n)，其中 n 是该值在数组中的出现次数

• 空间复杂度：O(n)，因为我们需要存储数组中每个值的索引列表，最坏情况下，所有的值都是相同的，因此存储空间为 O(n)

总结

这道题目通过引入 Map 和二分查找，使得频率查询的操作变得高效。通过将数组中每个值的出现位置存储起来，我们能够在查询时迅速找到符合条件的区间，并计算频率。与暴力遍历相比，这种方法能大幅减少查询时间，提高了查询效率。在解决此类区间查询问题时，利用预处理和二分查找是一个非常有效的策略。

希望这篇分享能为你带来启发！如果你有任何问题或建议，欢迎在评论区留言，与我共同交流探讨。