| comments | difficulty | edit_url | rating | source | tags | |||||
|---|---|---|---|---|---|---|---|---|---|---|
true |
中等 |
1702 |
第 268 场周赛 Q3 |
|
请你设计一个数据结构，它能求出给定子数组内一个给定值的 频率 。
子数组中一个值的 频率 指的是这个子数组中这个值的出现次数。
请你实现 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.length- 调用
query不超过105次。
我们用一个哈希表
在查询函数中，我们首先判断哈希表中是否存在给定的值。如果不存在，说明该值在数组中不存在，直接返回
时间复杂度方面，构造函数的时间复杂度为
class RangeFreqQuery:
def __init__(self, arr: List[int]):
self.g = defaultdict(list)
for i, x in enumerate(arr):
self.g[x].append(i)
def query(self, left: int, right: int, value: int) -> int:
idx = self.g[value]
l = bisect_left(idx, left)
r = bisect_left(idx, right + 1)
return r - l
# Your RangeFreqQuery object will be instantiated and called as such:
# obj = RangeFreqQuery(arr)
# param_1 = obj.query(left,right,value)class RangeFreqQuery {
private Map<Integer, List<Integer>> g = new HashMap<>();
public RangeFreqQuery(int[] arr) {
for (int i = 0; i < arr.length; ++i) {
g.computeIfAbsent(arr[i], k -> new ArrayList<>()).add(i);
}
}
public int query(int left, int right, int value) {
if (!g.containsKey(value)) {
return 0;
}
var idx = g.get(value);
int l = Collections.binarySearch(idx, left);
l = l < 0 ? -l - 1 : l;
int r = Collections.binarySearch(idx, right + 1);
r = r < 0 ? -r - 1 : r;
return r - l;
}
}
/**
* Your RangeFreqQuery object will be instantiated and called as such:
* RangeFreqQuery obj = new RangeFreqQuery(arr);
* int param_1 = obj.query(left,right,value);
*/class RangeFreqQuery {
public:
RangeFreqQuery(vector<int>& arr) {
for (int i = 0; i < arr.size(); ++i) {
g[arr[i]].push_back(i);
}
}
int query(int left, int right, int value) {
if (!g.contains(value)) {
return 0;
}
auto& idx = g[value];
auto l = lower_bound(idx.begin(), idx.end(), left);
auto r = lower_bound(idx.begin(), idx.end(), right + 1);
return r - l;
}
private:
unordered_map<int, vector<int>> g;
};
/**
* Your RangeFreqQuery object will be instantiated and called as such:
* RangeFreqQuery* obj = new RangeFreqQuery(arr);
* int param_1 = obj->query(left,right,value);
*/type RangeFreqQuery struct {
g map[int][]int
}
func Constructor(arr []int) RangeFreqQuery {
g := make(map[int][]int)
for i, v := range arr {
g[v] = append(g[v], i)
}
return RangeFreqQuery{g}
}
func (this *RangeFreqQuery) Query(left int, right int, value int) int {
if idx, ok := this.g[value]; ok {
l := sort.SearchInts(idx, left)
r := sort.SearchInts(idx, right+1)
return r - l
}
return 0
}
/**
* Your RangeFreqQuery object will be instantiated and called as such:
* obj := Constructor(arr);
* param_1 := obj.Query(left,right,value);
*/class RangeFreqQuery {
private g: Map<number, number[]> = new Map();
constructor(arr: number[]) {
for (let i = 0; i < arr.length; ++i) {
if (!this.g.has(arr[i])) {
this.g.set(arr[i], []);
}
this.g.get(arr[i])!.push(i);
}
}
query(left: number, right: number, value: number): number {
const idx = this.g.get(value);
if (!idx) {
return 0;
}
const l = _.sortedIndex(idx, left);
const r = _.sortedIndex(idx, right + 1);
return r - l;
}
}
/**
* Your RangeFreqQuery object will be instantiated and called as such:
* var obj = new RangeFreqQuery(arr)
* var param_1 = obj.query(left,right,value)
*/use std::collections::HashMap;
struct RangeFreqQuery {
g: HashMap<i32, Vec<usize>>,
}
impl RangeFreqQuery {
fn new(arr: Vec<i32>) -> Self {
let mut g = HashMap::new();
for (i, &value) in arr.iter().enumerate() {
g.entry(value).or_insert_with(Vec::new).push(i);
}
RangeFreqQuery { g }
}
fn query(&self, left: i32, right: i32, value: i32) -> i32 {
if let Some(idx) = self.g.get(&value) {
let l = idx.partition_point(|&x| x < left as usize);
let r = idx.partition_point(|&x| x <= right as usize);
return (r - l) as i32;
}
0
}
}/**
* @param {number[]} arr
*/
var RangeFreqQuery = function (arr) {
this.g = new Map();
for (let i = 0; i < arr.length; ++i) {
if (!this.g.has(arr[i])) {
this.g.set(arr[i], []);
}
this.g.get(arr[i]).push(i);
}
};
/**
* @param {number} left
* @param {number} right
* @param {number} value
* @return {number}
*/
RangeFreqQuery.prototype.query = function (left, right, value) {
const idx = this.g.get(value);
if (!idx) {
return 0;
}
const l = _.sortedIndex(idx, left);
const r = _.sortedIndex(idx, right + 1);
return r - l;
};
/**
* Your RangeFreqQuery object will be instantiated and called as such:
* var obj = new RangeFreqQuery(arr)
* var param_1 = obj.query(left,right,value)
*/public class RangeFreqQuery {
private Dictionary<int, List<int>> g;
public RangeFreqQuery(int[] arr) {
g = new Dictionary<int, List<int>>();
for (int i = 0; i < arr.Length; ++i) {
if (!g.ContainsKey(arr[i])) {
g[arr[i]] = new List<int>();
}
g[arr[i]].Add(i);
}
}
public int Query(int left, int right, int value) {
if (g.ContainsKey(value)) {
var idx = g[value];
int l = idx.BinarySearch(left);
int r = idx.BinarySearch(right + 1);
l = l < 0 ? -l - 1 : l;
r = r < 0 ? -r - 1 : r;
return r - l;
}
return 0;
}
}
/**
* Your RangeFreqQuery object will be instantiated and called as such:
* RangeFreqQuery obj = new RangeFreqQuery(arr);
* int param_1 = obj.Query(left, right, value);
*/