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]}

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

相关推荐

Geist字体家族：解决现代数字设计字体难题的完整方案

嵌入式视频处理中VPDMA通道分配与中断机制深度解析

TI编译器预处理与诊断控制：嵌入式开发构建优化实战

更多资讯

WTF-Solidity 极简入门：ERC20 代币标准详解与测试代币发行实战

基于Python和微信小程序的汽车改装报价系统设计与实现

TanStack Router 入门实战：从 basic 示例掌握路由配置、导航、参数与数据加载

ipatool：指定版本 IPA 下载工具实战指南

沃尔玛选品CLI工具实战指南：数据源、稳定性与场景化选型

Herdr 插件与 Socket API 完全指南：HERDR_BIN_PATH 可移植性技巧

今日更新

基于高阶循环谱的MPSK载波频率估计与MATLAB实现

MiniPdf方：.NET开源Office转PDF的高效解决方案

Solon AI v3.10：Java全栈智能体开发框架解析

本周精选

AI驱动的自动化专利分析平台技术解析

LeetCode-Go 题解：1252. Cells with Odd Values in a Matrix（奇数值单元格计数）双解法剖析

在线答疑系统Java毕设实战：Spring Boot前后端分离与状态流转

本月热门

基于YOLO的焊缝缺陷检测：从数据标注到工业部署全流程实践

分布式服务的决策记录

创业产品的首版范围

读完文章，想聊聊您的网站？