区间内查询数字的频率 | LeetCode-2080 | 二分查找

二分查找你学废了吗？快来看看这道题如何使用二分查找解决吧!

---

LeetCode链接：2080. 区间内查询数字的频率

---

1.题目描述

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

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

请你实现 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^5$
• $1 <= arr[i], value <= 10^4$
• 0 <= left <= right < arr.length
• 调用 query 不超过 $10^5$ 次。

2.题解

2.1 哈希集合+二分查找

class RangeFreqQuery {
    // 创建一个映射，用于存储每个数字在数组中的出现位置
    private Map<Integer, List<Integer>> map = new HashMap<>();

    // 构造函数，用于初始化对象并构建map
    public RangeFreqQuery(int[] arr) {
        // 遍历数组，记录每个数字出现的位置
        for (int i = 0; i < arr.length; i++) {
            int num = arr[i];
            // 如果map中没有该数字，初始化一个新的列表
            if(!map.containsKey(num)) map.put(num,new ArrayList<Integer>());
            map.get(num).add(i);
        }
    }

    // 查询函数，返回值为目标数字在指定范围内的出现次数
    public int query(int left, int right, int value) {
        if (!map.containsKey(value)) return 0;// 如果map中没有目标数字，直接返回0
        List<Integer> list = map.get(value);// 获取目标数字的所有出现位置列表
        
        // 使用二分查找找到左边界和右边界对应的索引
        int leftIndex = binarySearch(list, left, true);
        int rightIndex = binarySearch(list, right, false);
        
        // 计算并返回目标数字在指定范围内的出现次数
        return rightIndex - leftIndex + 1;
    }

    // 二分查找辅助函数，用于查找目标值的左边界或右边界索引
    private int binarySearch(List<Integer> list, int target, boolean findFirst) {
        int min = 0, max = list.size() - 1;
        while (min <= max) {
            int mid = min + (max - min) / 2;
            // 根据标志位选择合适的边界，继续缩小查找范围
            if (target < list.get(mid) || (findFirst && target <= list.get(mid))) {
                max = mid - 1;
            } else {
                min = mid + 1;
            }
        }
        // 返回左边界或右边界对应的索引
        return findFirst ? min : min - 1;
    }
}