DeepSeek LeetCode 3636. 查询超过阈值频率最高元素 Rust实现

核心解题思路这道题是静态区间众数查询问题。最优解法是分块预处理 位置列表二分查找1. 分块将数组分成大小为 √n 的块2. 预处理块间众数pmx[i][j] 表示从块 i 到块 j 的众数3. 位置列表每个元素的所有出现位置用于二分统计频率4. 查询优化候选众数 中间完整块的众数 左右零散部分的所有元素Rust 实现1. 方案一分块最优解rustuse std::collections::HashMap;use std::cmp::Ordering;impl Solution {pub fn subarray_majority(nums: Veci32, queries: VecVeci32) - Veci32 {let n nums.len();let size (n as f64).sqrt() as usize 1;let block_cnt (n size - 1) / size;// 1. 预处理每个元素的所有出现位置let mut pos: HashMapi32, Vecusize HashMap::new();for (i, num) in nums.iter().enumerate() {pos.entry(num).or_insert_with(Vec::new).push(i);}// 2. 预处理块间众数 pmx[i][j]let mut pmx vec![vec![0; block_cnt]; block_cnt];for i in 0..block_cnt {let mut cnt: HashMapi32, usize HashMap::new();let mut mode 0;let mut max_cnt 0;for j in i..block_cnt {let start j * size;let end std::cmp::min((j 1) * size, n);for k in start..end {let num nums[k];let c cnt.entry(num).or_insert(0);*c 1;let c *c;if c max_cnt || (c max_cnt num mode) {max_cnt c;mode num;}}pmx[i][j] mode;}}// 辅助函数统计元素 x 在区间 [l, r] 内的出现次数let count_freq |x: i32, l: usize, r: usize| - usize {if let Some(lst) pos.get(x) {let left lst.binary_search(l).unwrap_or_else(|e| e);let right lst.binary_search((r 1)).unwrap_or_else(|e| e);return right - left;}0};// 3. 处理每个查询let mut ans Vec::with_capacity(queries.len());for query in queries {let l query[0] as usize;let r query[1] as usize;let threshold query[2] as usize;let lb l / size;let rb r / size;// 同一块或相邻块直接暴力统计if lb rb || lb 1 rb {let mut cnt: HashMapi32, usize HashMap::new();let mut mode 0;let mut max_cnt 0;for i in l..r {let num nums[i];let c cnt.entry(num).or_insert(0);*c 1;let c *c;if c max_cnt || (c max_cnt num mode) {max_cnt c;mode num;}}ans.push(if max_cnt threshold { mode } else { -1 });continue;}// 候选众数中间块的众数 左右零散部分的所有元素let mut candidates Vec::new();candidates.push(pmx[lb 1][rb - 1]);// 左零散部分 [l, (lb1)*size - 1]for i in l..(lb 1) * size {candidates.push(nums[i]);}// 右零散部分 [rb*size, r]for i in rb * size..r {candidates.push(nums[i]);}// 去重优化candidates.sort_unstable();candidates.dedup();// 统计每个候选的频率let mut best_num -1;let mut best_freq 0;for num in candidates {let freq count_freq(num, l, r);if freq threshold {if freq best_freq || (freq best_freq num best_num) {best_freq freq;best_num num;}}}ans.push(best_num);}ans}}2. 方案二优化版使用 BTreeMap 保持顺序rustuse std::collections::{HashMap, BTreeMap};use std::cmp::Ordering;impl Solution {pub fn subarray_majority(nums: Veci32, queries: VecVeci32) - Veci32 {let n nums.len();let size (n as f64).sqrt() as usize 1;let block_cnt (n size - 1) / size;// 预处理位置列表let mut pos: HashMapi32, Vecusize HashMap::new();for (i, num) in nums.iter().enumerate() {pos.entry(num).or_insert_with(Vec::new).push(i);}// 预处理块间众数let mut pmx vec![vec![0; block_cnt]; block_cnt];for i in 0..block_cnt {let mut cnt: HashMapi32, usize HashMap::new();let mut mode 0;let mut max_cnt 0;for j in i..block_cnt {let start j * size;let end std::cmp::min((j 1) * size, n);for k in start..end {let num nums[k];let c cnt.entry(num).or_insert(0);*c 1;let c *c;if c max_cnt || (c max_cnt num mode) {max_cnt c;mode num;}}pmx[i][j] mode;}}// 统计频率的闭包let count_freq |x: i32, l: usize, r: usize| - usize {pos.get(x).map(|lst| {let left lst.binary_search(l).unwrap_or_else(|e| e);let right lst.binary_search((r 1)).unwrap_or_else(|e| e);right - left}).unwrap_or(0)};// 处理查询queries.into_iter().map(|q| {let l q[0] as usize;let r q[1] as usize;let threshold q[2] as usize;let lb l / size;let rb r / size;// 相邻块暴力if lb rb || lb 1 rb {let mut cnt: HashMapi32, usize HashMap::new();let mut mode 0;let mut max_cnt 0;for i in l..r {let num nums[i];let c cnt.entry(num).or_insert(0);*c 1;let c *c;if c max_cnt || (c max_cnt num mode) {max_cnt c;mode num;}}return if max_cnt threshold { mode } else { -1 };}// 构建候选集let mut candidates Vec::with_capacity((rb - lb 1) * 2 1);candidates.push(pmx[lb 1][rb - 1]);// 左右边界元素for i in l..(lb 1) * size {candidates.push(nums[i]);}for i in rb * size..r {candidates.push(nums[i]);}// 去重并排序candidates.sort_unstable();candidates.dedup();// 找最优解let mut best (-1, 0); // (num, freq)for num in candidates {let freq count_freq(num, l, r);if freq threshold (freq best.1 || (freq best.1 num best.0)) {best (num, freq);}}best.0}).collect()}}3. 方案三简单版适合小数据rustuse std::collections::HashMap;impl Solution {pub fn subarray_majority(nums: Veci32, queries: VecVeci32) - Veci32 {// 预处理每个元素的出现位置let mut pos: HashMapi32, Vecusize HashMap::new();for (i, num) in nums.iter().enumerate() {pos.entry(num).or_insert_with(Vec::new).push(i);}// 统计频率的闭包let count_freq |x: i32, l: usize, r: usize| - usize {if let Some(lst) pos.get(x) {let left lst.binary_search(l).unwrap_or_else(|e| e);let right lst.binary_search((r 1)).unwrap_or_else(|e| e);return right - left;}0};// 处理每个查询queries.iter().map(|q| {let l q[0] as usize;let r q[1] as usize;let threshold q[2] as usize;let mut best_num -1;let mut best_freq 0;// 遍历所有不同元素for (num, _) in pos.iter() {let freq count_freq(num, l, r);if freq threshold {if freq best_freq || (freq best_freq num best_num) {best_freq freq;best_num num;}}}best_num}).collect()}}复杂度分析方案 预处理时间 单次查询时间 空间复杂度分块 O(n√n) O(√n log n) O(n √n²) O(n)简单版 O(n) O(U log n) O(n)关键要点1. 分块大小sqrt(n) 平衡预处理和查询复杂度2. 位置列表使用二分查找快速统计频率3. 候选优化只需检查中间块众数和边界元素4. 去重候选列表去重减少重复统计5. Rust 特性使用 HashMap、Vec::binary_search、闭包等测试示例rust// 在 Solution 结构体中fn main() {let nums vec![1, 3, 2, 3, 3, 2, 2, 1];let queries vec![vec![0, 7, 3],vec![0, 4, 2],vec![1, 5, 3],];let result Solution::subarray_majority(nums, queries);println!({:?}, result); // 输出: [2, 3, -1]}