核心解题思路

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

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

C++ 实现

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

```cpp
#include <vector>
#include <unordered_map>
#include <cmath>
#include <algorithm>
#include <set>

using namespace std;

class Solution {
public:
    vector<int> subarrayMajority(vector<int>& nums, vector<vector<int>>& queries) {
        int n = nums.size();
        int size = (int)sqrt(n) + 1;
        int block_cnt = (n + size - 1) / size;
        
        // 1. 预处理每个元素的所有出现位置
        unordered_map<int, vector<int>> pos;
        for (int i = 0; i < n; i++) {
            pos[nums[i]].push_back(i);
        }
        
        // 2. 预处理块间众数 pmx[i][j]
        vector<vector<int>> pmx(block_cnt, vector<int>(block_cnt, 0));
        for (int i = 0; i < block_cnt; i++) {
            unordered_map<int, 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 vector<int>& lst = pos[x];
            return upper_bound(lst.begin(), lst.end(), r) - lower_bound(lst.begin(), lst.end(), l);
        };
        
        // 3. 处理每个查询
        vector<int> 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_map<int, 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;
            }
            
            // 候选众数：中间块的众数 + 左右零散部分的所有元素
            vector<int> candidates;
            candidates.reserve((rb - lb) * 2 + 1);
            candidates.push_back(pmx[lb + 1][rb - 1]);  // 中间完整块的众数
            
            // 左零散部分 [l, (lb+1)*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 <algorithm>

using namespace std;

class Solution {
public:
    vector<int> subarrayMajority(vector<int>& nums, vector<vector<int>>& queries) {
        int n = nums.size();
        int size = (int)sqrt(n) + 1;
        int block_cnt = (n + size - 1) / size;
        
        // 预处理位置列表
        unordered_map<int, vector<int>> pos;
        for (int i = 0; i < n; i++) {
            pos[nums[i]].push_back(i);
        }
        
        // 预处理块间众数
        vector<vector<int>> pmx(block_cnt, vector<int>(block_cnt, 0));
        vector<unordered_map<int, int>> block_cnts(block_cnt);
        
        for (int i = 0; i < block_cnt; i++) {
            int mode = 0, max_cnt = 0;
            unordered_map<int, 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);
        };
        
        vector<int> 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_map<int, 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;
            }
            
            // 收集候选
            vector<int> 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 <algorithm>

using namespace std;

class Solution {
public:
    vector<int> subarrayMajority(vector<int>& nums, vector<vector<int>>& queries) {
        // 预处理每个元素的出现位置
        unordered_map<int, vector<int>> pos;
        for (int i = 0; i < nums.size(); i++) {
            pos[nums[i]].push_back(i);
        }
        
        vector<int> ans;
        ans.reserve(queries.size());
        
        // 统计频率的 lambda
        auto 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 <algorithm>

using namespace std;

class Solution {
public:
    vector<int> subarrayMajority(vector<int>& nums, vector<vector<int>>& queries) {
        int n = nums.size();
        
        // 离散化
        vector<int> sorted = nums;
        sort(sorted.begin(), sorted.end());
        sorted.erase(unique(sorted.begin(), sorted.end()), sorted.end());
        
        unordered_map<int, int> compress;
        for (int i = 0; i < sorted.size(); i++) {
            compress[sorted[i]] = i;
        }
        
        // 位置列表（使用 vector，提高 cache 命中率）
        vector<vector<int>> 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;
        
        // 预处理块间众数（存储原始值）
        vector<vector<int>> pmx(block_cnt, vector<int>(block_cnt, 0));
        for (int i = 0; i < block_cnt; i++) {
            vector<int> 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);
        };
        
        vector<int> 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) {
                vector<int> 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;
            }
            
            vector<int> 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 <vector>

int main() {
    Solution sol;
    vector<int> nums = {1, 3, 2, 3, 3, 2, 2, 1};
    vector<vector<int>> queries = {
        {0, 7, 3},
        {0, 4, 2},
        {1, 5, 3}
    };
    
    vector<int> result = sol.subarrayMajority(nums, queries);
    
    for (int x : result) {
        cout << x << " ";
    }
    cout << endl;  // 输出: 2 3 -1
    
    return 0;
}
```