文章

[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 的键是数组中的值,值是该值在数组中所有出现位置的索引列表

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

代码实现

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

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

License:  CC BY 4.0