核心解题思路

这道题是静态区间众数查询问题。最优解法是分块预处理 + 位置列表二分查找：

1. 分块：将数组分成大小为 √n 的块
2. 预处理块间众数：pmx[i][j] 表示从块 i 到块 j 的众数
3. 位置列表：每个元素的所有出现位置，用于二分统计频率
4. 查询优化：候选众数 = 中间完整块的众数 + 左右零散部分的所有元素

Rust 实现

1. 方案一：分块（最优解）

```rust
use std::collections::HashMap;
use std::cmp::Ordering;

impl Solution {
    pub fn subarray_majority(nums: Vec<i32>, queries: Vec<Vec<i32>>) -> Vec<i32> {
        let n = nums.len();
        let size = (n as f64).sqrt() as usize + 1;
        let block_cnt = (n + size - 1) / size;
        
        // 1. 预处理每个元素的所有出现位置
        let mut pos: HashMap<i32, Vec<usize>> = 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: HashMap<i32, 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: HashMap<i32, 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, (lb+1)*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 保持顺序）

```rust
use std::collections::{HashMap, BTreeMap};
use std::cmp::Ordering;

impl Solution {
    pub fn subarray_majority(nums: Vec<i32>, queries: Vec<Vec<i32>>) -> Vec<i32> {
        let n = nums.len();
        let size = (n as f64).sqrt() as usize + 1;
        let block_cnt = (n + size - 1) / size;
        
        // 预处理位置列表
        let mut pos: HashMap<i32, Vec<usize>> = 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: HashMap<i32, 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: HashMap<i32, 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. 方案三：简单版（适合小数据）

```rust
use std::collections::HashMap;

impl Solution {
    pub fn subarray_majority(nums: Vec<i32>, queries: Vec<Vec<i32>>) -> Vec<i32> {
        // 预处理每个元素的出现位置
        let mut pos: HashMap<i32, Vec<usize>> = 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]
}
```