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：
输入： ["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 <= 1051 <= arr[i], value <= 1040 <= left <= right < arr.lengthquery 不超过 105 次。原站题解
javascript 解法, 执行用时: 130 ms, 内存消耗: 95.9 MB, 提交时间: 2025-02-18 07:45:25
var RangeFreqQuery = function(arr) {
this.pos = {};
for (let i = 0; i < arr.length; i++) {
if (this.pos[arr[i]] === undefined) {
this.pos[arr[i]] = [];
}
this.pos[arr[i]].push(i);
}
};
RangeFreqQuery.prototype.query = function(left, right, value) {
const a = this.pos[value];
if (a === undefined) {
return 0;
}
// > right 等价于 >= right+1
return lowerBound(a, right + 1) - lowerBound(a, left);
};
// 见 https://www.bilibili.com/video/BV1AP41137w7/
var lowerBound = function(a, target) {
let left = -1, right = a.length; // 开区间 (left, right)
while (left + 1 < right) { // 区间不为空
const mid = Math.floor((left + right) / 2);
if (a[mid] >= target) {
right = mid; // 范围缩小到 (left, mid)
} else {
left = mid; // 范围缩小到 (mid, right)
}
}
return right;
}
/**
* Your RangeFreqQuery object will be instantiated and called as such:
* var obj = new RangeFreqQuery(arr)
* var param_1 = obj.query(left,right,value)
*/
rust 解法, 执行用时: 35 ms, 内存消耗: 79.3 MB, 提交时间: 2025-02-18 07:45:06
use std::collections::HashMap;
struct RangeFreqQuery {
pos: HashMap<i32, Vec<usize>>,
}
impl RangeFreqQuery {
fn new(arr: Vec<i32>) -> Self {
let mut pos = HashMap::new();
for (i, &x) in arr.iter().enumerate() {
pos.entry(x).or_insert(vec![]).push(i);
}
Self { pos }
}
fn query(&self, left: i32, right: i32, value: i32) -> i32 {
if let Some(a) = self.pos.get(&value) {
let p = a.partition_point(|&i| i < left as usize);
let q = a.partition_point(|&i| i <= right as usize);
(q - p) as _
} else {
0
}
}
}
/**
* Your RangeFreqQuery object will be instantiated and called as such:
* let obj = RangeFreqQuery::new(arr);
* let ret_1: i32 = obj.query(left, right, value);
*/
java 解法, 执行用时: 128 ms, 内存消耗: 129.4 MB, 提交时间: 2025-02-18 07:44:23
class RangeFreqQuery {
private final Map<Integer, List<Integer>> pos = new HashMap<>();
public RangeFreqQuery(int[] arr) {
for (int i = 0; i < arr.length; i++) {
pos.computeIfAbsent(arr[i], k -> new ArrayList<>()).add(i);
}
}
public int query(int left, int right, int value) {
List<Integer> a = pos.get(value);
if (a == null) {
return 0;
}
// > right 等价于 >= right+1
return lowerBound(a, right + 1) - lowerBound(a, left);
}
// 开区间写法
// 请看 https://www.bilibili.com/video/BV1AP41137w7/
private int lowerBound(List<Integer> a, int target) {
// 开区间 (left, right)
int left = -1;
int right = a.size();
while (left + 1 < right) { // 区间不为空
// 循环不变量：
// a[left] < target
// a[right] >= target
int mid = (left + right) >>> 1;
if (a.get(mid) < target) {
left = mid; // 范围缩小到 (mid, right)
} else {
right = mid; // 范围缩小到 (left, mid)
}
}
return right; // right 是最小的满足 a[right] >= target 的下标
}
}
/**
* Your RangeFreqQuery object will be instantiated and called as such:
* RangeFreqQuery obj = new RangeFreqQuery(arr);
* int param_1 = obj.query(left,right,value);
*/
cpp 解法, 执行用时: 89 ms, 内存消耗: 235.6 MB, 提交时间: 2025-02-18 07:44:02
class RangeFreqQuery {
unordered_map<int, vector<int>> pos;
public:
RangeFreqQuery(vector<int>& arr) {
for (int i = 0; i < arr.size(); i++) {
pos[arr[i]].push_back(i);
}
}
int query(int left, int right, int value) {
// 不推荐写 a = pos[value]，如果 value 不在 pos 中会插入 value
auto it = pos.find(value);
if (it == pos.end()) {
return 0;
}
auto& a = it->second;
return ranges::upper_bound(a, right) - ranges::lower_bound(a, left);
}
};
/**
* Your RangeFreqQuery object will be instantiated and called as such:
* RangeFreqQuery* obj = new RangeFreqQuery(arr);
* int param_1 = obj->query(left,right,value);
*/
golang 解法, 执行用时: 604 ms, 内存消耗: 80.6 MB, 提交时间: 2023-04-19 10:00:01
type RangeFreqQuery struct{ pos [1e4 + 1]sort.IntSlice }
func Constructor(arr []int) (q RangeFreqQuery) {
for i, value := range arr {
q.pos[value] = append(q.pos[value], i) // 统计 value 在 arr 中的所有下标位置
}
return
}
func (q *RangeFreqQuery) Query(left, right, value int) int {
p := q.pos[value] // value 在 arr 中的所有下标位置
return p[p.Search(left):].Search(right + 1) // 在下标位置上二分，求 [left,right] 之间的下标个数，即为 value 的频率
}
/**
* Your RangeFreqQuery object will be instantiated and called as such:
* obj := Constructor(arr);
* param_1 := obj.Query(left,right,value);
*/
python3 解法, 执行用时: 604 ms, 内存消耗: 54.7 MB, 提交时间: 2023-04-19 09:59:30
class RangeFreqQuery:
def __init__(self, arr: List[int]):
# 数值为键，出现下标数组为值的哈希表
self.occurence = defaultdict(list)
# 顺序遍历数组初始化哈希表
n = len(arr)
for i in range(n):
self.occurence[arr[i]].append(i)
def query(self, left: int, right: int, value: int) -> int:
# 查找对应的出现下标数组，不存在则为空
pos = self.occurence[value]
# 两次二分查找计算子数组内出现次数
l = bisect_left(pos, left)
r = bisect_right(pos, right)
return r - l
# Your RangeFreqQuery object will be instantiated and called as such:
# obj = RangeFreqQuery(arr)
# param_1 = obj.query(left,right,value)