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

解题过程

频率相关的问题，大概率和哈希表有关，这题的困难之处也在于如何构造哈希表。
实际上需要建立的是每个元素，与它所有可能下标组成的列表之间的映射。
有了这样的数据之后，就可以用二分法确定要求的范围内到底有多少待查询元素存在了。

具体实现

class RangeFreqQuery {
    private final Map<Integer, List<Integer>> map = new HashMap<>();

    public RangeFreqQuery(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            map.computeIfAbsent(arr[i], key -> new ArrayList<>()).add(i);
        }
    }
    
    public int query(int left, int right, int value) {
        List<Integer> positions = map.get(value);
        if (positions == null) {
            return 0;
        }
        return binarySearch(positions, right + 1) - binarySearch(positions, left);
    }

    private int binarySearch(List<Integer> list, int target) {
        int left = 0;
        int right = list.size();
        while (left < right) {
            int mid = left + ((right - left) >>> 1);
            if (list.get(mid) < target) {
                left = mid + 1;
            } else {
                right = mid;
            }
        }
        return left;
    }
}

/**
 * Your RangeFreqQuery object will be instantiated and called as such:
 * RangeFreqQuery obj = new RangeFreqQuery(arr);
 * int param_1 = obj.query(left,right,value);
 */