当前位置:网站首页>2022-07-05: given an array, you want to query the maximum value in any range at any time. If it is only established according to the initial array and has not been modified in the future, the RMQ meth
2022-07-05: given an array, you want to query the maximum value in any range at any time. If it is only established according to the initial array and has not been modified in the future, the RMQ meth
2022-07-05 22:05:00 【Fuda frame constructor daily question】
2022-07-05: Given an array , Want to query the maximum value in any range at any time .
If it's just based on the initial array 、 And it has not been modified in the future ,
that RMQ Method is better than line segment tree method , Time complexity O(NlogN), Extra space complexity O(NlogN).
From little red book .3.13 written examination .
answer 2022-07-05:
RMQ Range maximum and minimum query , Update not supported .
Spatial complexity :O(N*logN).
Query complexity :O(1).
The code to use rust To write . The code is as follows :
use rand::Rng;
fn main() {
let nn: i32 = 150;
let vv = 200;
let test_time_out = 20000;
let test_time_in = 200;
println!(" Beginning of the test ");
for i in 0..test_time_out {
let n = rand::thread_rng().gen_range(0, nn) + 1;
let mut arr = random_array(n, vv);
let mut arr2=arr.clone();
let m = arr.len() as i32;
let mut rmq = RMQ::new(&mut arr);
let mut right = Right::new(&mut arr2);
for _ in 0..test_time_in {
let a = rand::thread_rng().gen_range(0, m) + 1;
let b = rand::thread_rng().gen_range(0, m) + 1;
let l = get_min(a, b);
let r = get_max(a, b);
let ans1 = rmq.max(l, r);
let ans2 = right.max(l, r);
if ans1 != ans2 {
println!(" Something went wrong !{}", i);
println!("ans1 = {}", ans1);
println!("ans2 = {}", ans2);
break;
}
}
}
println!(" End of test ");
}
pub struct RMQ {
pub max: Vec<Vec<i32>>,
}
impl RMQ {
// Subscript must be from 1 Start , There's no reason ! It's a convention !
pub fn new(arr: &mut Vec<i32>) -> Self {
// length !
let n = arr.len() as i32;
let mut ans: RMQ = RMQ {
max: vec![] };
// 2 Several power , You can take n
let k = ans.power2(n);
// n*logn
let mut max: Vec<Vec<i32>> = vec![];
for i in 0..n + 1 {
max.push(vec![]);
for _ in 0..k + 1 {
max[i as usize].push(0);
}
}
for i in 1..=n {
// i 0: From the subscript i Start , Continuous downward 2 Of 0 The number of power , in , Maximum
// 1...1 individual
// 2...1 individual
// 3...1 individual
max[i as usize][0] = arr[(i - 1) as usize];
}
ans.max = max;
let mut j = 1;
while (1 << j) <= n {
// i... Successive 、2 Of 1 The number of power , This range , Maximum
// i... Successive 、2 Of 2 The number of power , This range , Maximum
// i... Successive 、2 Of 3 The number of power , This range , Maximum
let mut i = 1;
while i + (1 << j) - 1 <= n {
// max[10][3]
// Subscript 10 Start , Successive 8 Number , What is the maximum
// 1) max[10][2]
// 2) max[14][2]
ans.max[i as usize][j as usize] = get_max(
ans.max[i as usize][(j - 1) as usize],
ans.max[(i + (1 << (j - 1))) as usize][(j - 1) as usize],
);
i += 1;
}
j += 1;
}
return ans;
}
pub fn max(&mut self, l: i32, r: i32) -> i32 {
// l...r -> r - l + 1 -> 2 Which power of is closest to it !
let k = self.power2(r - l + 1);
return get_max(
self.max[l as usize][k as usize],
self.max[(r - (1 << k) + 1) as usize][k as usize],
);
}
fn power2(&mut self, m: i32) -> i32 {
let mut ans = 0;
while (1 << ans) <= (m >> 1) {
ans += 1;
}
return ans;
}
}
// In order to test
pub struct Right {
pub max: Vec<Vec<i32>>,
}
impl Right {
pub fn new(arr: &mut Vec<i32>) -> Self {
let n = arr.len() as i32;
let mut max: Vec<Vec<i32>> = vec![];
for i in 0..n + 1 {
max.push(vec![]);
for _ in 0..n + 1 {
max[i as usize].push(0);
}
}
for l in 1..=n {
max[l as usize][l as usize] = arr[(l - 1) as usize];
for r in l + 1..=n {
max[l as usize][r as usize] =
get_max(max[l as usize][(r - 1) as usize], arr[(r - 1) as usize]);
}
}
Self {
max }
}
pub fn max(&mut self, l: i32, r: i32) -> i32 {
self.max[l as usize][r as usize]
}
}
fn get_max<T: Clone + Copy + std::cmp::PartialOrd>(a: T, b: T) -> T {
if a > b {
a
} else {
b
}
}
fn get_min<T: Clone + Copy + std::cmp::PartialOrd>(a: T, b: T) -> T {
if a < b {
a
} else {
b
}
}
// In order to test
fn random_array(n: i32, v: i32) -> Vec<i32> {
let mut arr: Vec<i32> = vec![];
for _i in 0..n {
arr.push(rand::thread_rng().gen_range(0, v));
}
return arr;
}
The results are as follows :
边栏推荐
- The American Championship is about to start. Are you ready?
- 华为游戏多媒体服务调用屏蔽指定玩家语音方法,返回错误码3010
- PIP install beatifulsoup4 installation failed
- An exception occurred in Huawei game multimedia calling the room switching method internal system error Reason:90000017
- Shell script, awk condition judgment and logic comparison &||
- Alternating merging strings of leetcode simple questions
- 从零开始实现lmax-Disruptor队列(四)多线程生产者MultiProducerSequencer原理解析
- Cross end solutions to improve development efficiency
- Interprocess communication in the "Chris Richardson microservice series" microservice architecture
- Leetcode simple question: check whether each row and column contain all integers
猜你喜欢
Recovery technology with checkpoints
[Yugong series] go teaching course in July 2022 004 go code Notes
Business learning of mall commodity module
装饰器学习01
Serializability of concurrent scheduling
Leetcode simple question: the minimum cost of buying candy at a discount
数据泄露怎么办?'华生·K'7招消灭安全威胁
元宇宙中的三大“派系”
boundary IoU 的计算方式
Oracle triggers
随机推荐
Decorator learning 01
如何组织一场实战攻防演练
How can Huawei online match improve the success rate of player matching
科技云报道荣膺全球云计算大会“云鼎奖”2013-2022十周年特别贡献奖
Huawei game multimedia service calls the method of shielding the voice of the specified player, and the error code 3010 is returned
Pl/sql basic case
Dbeaver executes multiple insert into error processing at the same time
Deeply convinced plan X - network protocol basic DNS
Microservice link risk analysis
Blocking protocol for concurrency control
多家呼吸机巨头产品近期被一级召回 呼吸机市场仍在增量竞争
Cross end solutions to improve development efficiency
Database recovery strategy
【愚公系列】2022年7月 Go教学课程 004-Go代码注释
Basic grammar of interview (Part 1)
数博会精彩回顾 | 彰显科研实力,中创算力荣获数字化影响力企业奖
Implementing Lmax disruptor queue from scratch (IV) principle analysis of multithreaded producer multiproducersequencer
POJ 3237 tree (tree chain splitting)
Overview of database recovery
Installation of VMware Workstation