核心解题思路这道题是静态区间众数查询问题。最优解法是分块预处理 位置列表二分查找1. 分块将数组分成大小为 √n 的块2. 预处理块间众数pmx[i][j] 表示从块 i 到块 j 的众数3. 位置列表每个元素的所有出现位置用于二分统计频率4. 查询优化候选众数 中间完整块的众数 左右零散部分的所有元素C 实现1. 方案一分块最优解cpp#include vector#include unordered_map#include cmath#include algorithm#include setusing namespace std;class Solution {public:vectorint subarrayMajority(vectorint nums, vectorvectorint queries) {int n nums.size();int size (int)sqrt(n) 1;int block_cnt (n size - 1) / size;// 1. 预处理每个元素的所有出现位置unordered_mapint, vectorint pos;for (int i 0; i n; i) {pos[nums[i]].push_back(i);}// 2. 预处理块间众数 pmx[i][j]vectorvectorint pmx(block_cnt, vectorint(block_cnt, 0));for (int i 0; i block_cnt; i) {unordered_mapint, int cnt;int mode 0, max_cnt 0;for (int j i; j block_cnt; j) {int start j * size;int end min((j 1) * size, n);for (int k start; k end; k) {int num nums[k];int c cnt[num];if (c max_cnt || (c max_cnt num mode)) {max_cnt c;mode num;}}pmx[i][j] mode;}}// 辅助函数统计元素 x 在区间 [l, r] 内的出现次数auto countFreq [](int x, int l, int r) - int {if (pos.find(x) pos.end()) return 0;const vectorint lst pos[x];return upper_bound(lst.begin(), lst.end(), r) - lower_bound(lst.begin(), lst.end(), l);};// 3. 处理每个查询vectorint ans;ans.reserve(queries.size());for (const auto q : queries) {int l q[0], r q[1], threshold q[2];int lb l / size, rb r / size;// 同一块或相邻块直接暴力统计if (lb rb || lb 1 rb) {unordered_mapint, int cnt;int mode 0, max_cnt 0;for (int i l; i r; i) {int num nums[i];int c cnt[num];if (c max_cnt || (c max_cnt num mode)) {max_cnt c;mode num;}}ans.push_back(max_cnt threshold ? mode : -1);continue;}// 候选众数中间块的众数 左右零散部分的所有元素vectorint candidates;candidates.reserve((rb - lb) * 2 1);candidates.push_back(pmx[lb 1][rb - 1]); // 中间完整块的众数// 左零散部分 [l, (lb1)*size - 1]for (int i l; i (lb 1) * size; i) {candidates.push_back(nums[i]);}// 右零散部分 [rb*size, r]for (int i rb * size; i r; i) {candidates.push_back(nums[i]);}// 去重优化sort(candidates.begin(), candidates.end());candidates.erase(unique(candidates.begin(), candidates.end()), candidates.end());// 统计每个候选的频率int best_num -1, best_freq 0;for (int num : candidates) {int freq countFreq(num, l, r);if (freq threshold) {if (freq best_freq || (freq best_freq num best_num)) {best_freq freq;best_num num;}}}ans.push_back(best_num);}return ans;}};2. 方案二内存优化版减少 map 开销cpp#include vector#include unordered_map#include cmath#include algorithmusing namespace std;class Solution {public:vectorint subarrayMajority(vectorint nums, vectorvectorint queries) {int n nums.size();int size (int)sqrt(n) 1;int block_cnt (n size - 1) / size;// 预处理位置列表unordered_mapint, vectorint pos;for (int i 0; i n; i) {pos[nums[i]].push_back(i);}// 预处理块间众数vectorvectorint pmx(block_cnt, vectorint(block_cnt, 0));vectorunordered_mapint, int block_cnts(block_cnt);for (int i 0; i block_cnt; i) {int mode 0, max_cnt 0;unordered_mapint, int cnt;for (int j i; j block_cnt; j) {int start j * size;int end min((j 1) * size, n);for (int k start; k end; k) {int num nums[k];cnt[num];if (cnt[num] max_cnt || (cnt[num] max_cnt num mode)) {max_cnt cnt[num];mode num;}}pmx[i][j] mode;}}// 统计频率函数auto getFreq [](int x, int l, int r) - int {auto it pos.find(x);if (it pos.end()) return 0;const auto vec it-second;return upper_bound(vec.begin(), vec.end(), r) -lower_bound(vec.begin(), vec.end(), l);};vectorint ans;ans.reserve(queries.size());for (const auto q : queries) {int l q[0], r q[1], threshold q[2];int lb l / size, rb r / size;// 相邻块暴力统计if (lb rb || lb 1 rb) {unordered_mapint, int cnt;int mode 0, max_cnt 0;for (int i l; i r; i) {int num nums[i];cnt[num];if (cnt[num] max_cnt || (cnt[num] max_cnt num mode)) {max_cnt cnt[num];mode num;}}ans.push_back(max_cnt threshold ? mode : -1);continue;}// 收集候选vectorint candidates;candidates.reserve((rb - lb 1) * 2);candidates.push_back(pmx[lb 1][rb - 1]);for (int i l; i (lb 1) * size; i) {candidates.push_back(nums[i]);}for (int i rb * size; i r; i) {candidates.push_back(nums[i]);}sort(candidates.begin(), candidates.end());candidates.erase(unique(candidates.begin(), candidates.end()), candidates.end());int best -1, bestFreq 0;for (int num : candidates) {int freq getFreq(num, l, r);if (freq threshold (freq bestFreq || (freq bestFreq num best))) {best num;bestFreq freq;}}ans.push_back(best);}return ans;}};3. 方案三简单版适合小数据cpp#include vector#include unordered_map#include algorithmusing namespace std;class Solution {public:vectorint subarrayMajority(vectorint nums, vectorvectorint queries) {// 预处理每个元素的出现位置unordered_mapint, vectorint pos;for (int i 0; i nums.size(); i) {pos[nums[i]].push_back(i);}vectorint ans;ans.reserve(queries.size());// 统计频率的 lambdaauto countFreq [](int x, int l, int r) - int {if (pos.find(x) pos.end()) return 0;const auto vec pos[x];return upper_bound(vec.begin(), vec.end(), r) -lower_bound(vec.begin(), vec.end(), l);};// 处理每个查询for (const auto q : queries) {int l q[0], r q[1], threshold q[2];int bestNum -1, bestFreq 0;// 遍历所有不同元素for (const auto [num, _] : pos) {int freq countFreq(num, l, r);if (freq threshold) {if (freq bestFreq || (freq bestFreq num bestNum)) {bestFreq freq;bestNum num;}}}ans.push_back(bestNum);}return ans;}};4. 方案四使用 vector 优化离散化cpp#include vector#include unordered_map#include cmath#include algorithmusing namespace std;class Solution {public:vectorint subarrayMajority(vectorint nums, vectorvectorint queries) {int n nums.size();// 离散化vectorint sorted nums;sort(sorted.begin(), sorted.end());sorted.erase(unique(sorted.begin(), sorted.end()), sorted.end());unordered_mapint, int compress;for (int i 0; i sorted.size(); i) {compress[sorted[i]] i;}// 位置列表使用 vector提高 cache 命中率vectorvectorint pos(sorted.size());for (int i 0; i n; i) {pos[compress[nums[i]]].push_back(i);}int size (int)sqrt(n) 1;int block_cnt (n size - 1) / size;// 预处理块间众数存储原始值vectorvectorint pmx(block_cnt, vectorint(block_cnt, 0));for (int i 0; i block_cnt; i) {vectorint cnt(sorted.size(), 0);int mode 0, max_cnt 0;for (int j i; j block_cnt; j) {int start j * size;int end min((j 1) * size, n);for (int k start; k end; k) {int idx compress[nums[k]];cnt[idx];if (cnt[idx] max_cnt || (cnt[idx] max_cnt nums[k] mode)) {max_cnt cnt[idx];mode nums[k];}}pmx[i][j] mode;}}// 统计频率函数auto getFreq [](int x, int l, int r) - int {int idx compress[x];const auto vec pos[idx];return upper_bound(vec.begin(), vec.end(), r) -lower_bound(vec.begin(), vec.end(), l);};vectorint ans;ans.reserve(queries.size());for (const auto q : queries) {int l q[0], r q[1], threshold q[2];int lb l / size, rb r / size;if (lb rb || lb 1 rb) {vectorint cnt(sorted.size(), 0);int mode 0, max_cnt 0;for (int i l; i r; i) {int idx compress[nums[i]];cnt[idx];if (cnt[idx] max_cnt || (cnt[idx] max_cnt nums[i] mode)) {max_cnt cnt[idx];mode nums[i];}}ans.push_back(max_cnt threshold ? mode : -1);continue;}vectorint candidates;candidates.reserve((rb - lb) * 2 1);candidates.push_back(pmx[lb 1][rb - 1]);for (int i l; i (lb 1) * size; i) {candidates.push_back(nums[i]);}for (int i rb * size; i r; i) {candidates.push_back(nums[i]);}sort(candidates.begin(), candidates.end());candidates.erase(unique(candidates.begin(), candidates.end()), candidates.end());int best -1, bestFreq 0;for (int num : candidates) {int freq getFreq(num, l, r);if (freq threshold (freq bestFreq || (freq bestFreq num best))) {best num;bestFreq freq;}}ans.push_back(best);}return ans;}};复杂度分析方案 预处理时间 单次查询时间 空间复杂度分块 O(n√n) O(√n log n) O(n √n²) O(n)简单版 O(n) O(U log n) O(n)离散化版 O(n√n) O(√n log n) O(n)关键要点1. 分块大小sqrt(n) 平衡预处理和查询复杂度2. 位置列表 二分快速统计任意元素在区间内的出现次数3. 候选优化只需检查中间块众数 边界元素4. 去重避免重复统计相同元素5. C 优化· 使用 unordered_map 存储位置列表· 使用 vector::reserve 预分配空间· 使用 lower_bound / upper_bound 二分查找· 离散化优化内存和 cache测试示例cpp#include iostream#include vectorint main() {Solution sol;vectorint nums {1, 3, 2, 3, 3, 2, 2, 1};vectorvectorint queries {{0, 7, 3},{0, 4, 2},{1, 5, 3}};vectorint result sol.subarrayMajority(nums, queries);for (int x : result) {cout x ;}cout endl; // 输出: 2 3 -1return 0;}