建设厅八大员_多媒体网页设计_写软文的app_百度搜索资源平台token

问题背景

请你设计一个数据结构，它能求出给定子数组内一个给定值的 频率 。
子数组中一个值的 频率 指的是这个子数组中这个值的出现次数。
请你实现 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);*/