当前位置:网站首页>2022-07-05:给定一个数组,想随时查询任何范围上的最大值。 如果只是根据初始数组建立、并且以后没有修改, 那么RMQ方法比线段树方法好实现,时间复杂度O(N*logN),额外空间复杂度O(N*
2022-07-05:给定一个数组,想随时查询任何范围上的最大值。 如果只是根据初始数组建立、并且以后没有修改, 那么RMQ方法比线段树方法好实现,时间复杂度O(N*logN),额外空间复杂度O(N*
2022-07-05 22:03:00 【福大大架构师每日一题】
2022-07-05:给定一个数组,想随时查询任何范围上的最大值。
如果只是根据初始数组建立、并且以后没有修改,
那么RMQ方法比线段树方法好实现,时间复杂度O(NlogN),额外空间复杂度O(NlogN)。
来自小红书。3.13笔试。
答案2022-07-05:
RMQ范围最大值和最小值查询,不支持更新。
空间复杂度:O(N*logN)。
查询复杂度:O(1)。
代码用rust编写。代码如下:
use rand::Rng;
fn main() {
let nn: i32 = 150;
let vv = 200;
let test_time_out = 20000;
let test_time_in = 200;
println!("测试开始");
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!("出错了!{}", i);
println!("ans1 = {}", ans1);
println!("ans2 = {}", ans2);
break;
}
}
}
println!("测试结束");
}
pub struct RMQ {
pub max: Vec<Vec<i32>>,
}
impl RMQ {
// 下标一定要从1开始,没有道理!就是约定俗成!
pub fn new(arr: &mut Vec<i32>) -> Self {
// 长度!
let n = arr.len() as i32;
let mut ans: RMQ = RMQ {
max: vec![] };
// 2的几次方,可以拿下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:从下标i开始,往下连续的2的0次方个数,中,最大值
// 1...1个
// 2...1个
// 3...1个
max[i as usize][0] = arr[(i - 1) as usize];
}
ans.max = max;
let mut j = 1;
while (1 << j) <= n {
// i...连续的、2的1次方个数,这个范围,最大值
// i...连续的、2的2次方个数,这个范围,最大值
// i...连续的、2的3次方个数,这个范围,最大值
let mut i = 1;
while i + (1 << j) - 1 <= n {
// max[10][3]
// 下标10开始,连续的8个数,最大值是多少
// 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的哪个次方最接近它!
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;
}
}
// 为了测试
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
}
}
// 为了测试
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;
}
执行结果如下:
边栏推荐
- Huawei game multimedia service calls the method of shielding the voice of the specified player, and the error code 3010 is returned
- 装饰器学习01
- 初级软件测试必问面试题
- How to use tensorflow2 for cat and dog classification and recognition
- 笔记本电脑蓝牙怎么用来连接耳机
- 从零开始实现lmax-Disruptor队列(四)多线程生产者MultiProducerSequencer原理解析
- oracle 控制文件的多路复用
- A trip to Suzhou during the Dragon Boat Festival holiday
- How to develop and introduce applet plug-ins
- Form artifact
猜你喜欢
ICMP introduction
Oracle检查点队列–实例崩溃恢复原理剖析
AD637使用笔记
Decorator learning 01
The American Championship is about to start. Are you ready?
Experienced inductance manufacturers tell you what makes the inductance noisy. Inductance noise is a common inductance fault. If the used inductance makes noise, you don't have to worry. You just need
Two stage locking protocol for concurrency control
Ad637 notes d'utilisation
Talking about MySQL index
Reptile practice
随机推荐
Cross end solutions to improve development efficiency
总结出现2xx、3xx、4xx、5xx状态码的原因
HDU 4391 Paint The Wall 段树(水
EBS Oracle 11g cloning steps (single node)
元宇宙中的三大“派系”
Experienced inductance manufacturers tell you what makes the inductance noisy. Inductance noise is a common inductance fault. If the used inductance makes noise, you don't have to worry. You just need
Drawing HSV color wheel with MATLAB
Oracle检查点队列–实例崩溃恢复原理剖析
Advantages of robot framework
How to use tensorflow2 for cat and dog classification and recognition
Code bug correction, char is converted to int high-order symbol extension, resulting in changes in positivity and negativity and values. Int num = (int) (unsigned int) a, which will occur in older com
如何向mongoDB中添加新的字段附代码(全)
让开发效率提升的跨端方案
从零开始实现lmax-Disruptor队列(四)多线程生产者MultiProducerSequencer原理解析
oracle 控制文件的多路复用
Detailed explanation of memset() function usage
Win11缺少dll文件怎么办?Win11系统找不到dll文件修复方法
微服务链路风险分析
K210 learning notes (IV) k210 runs multiple models at the same time
Summarize the reasons for 2XX, 3xx, 4xx, 5xx status codes