3636. 阈值多数查询

Hard

题目描述

给定一个长度为 n 的整数数组 nums 和一个查询数组 queries，其中 queries[i] = [li, ri, thresholdi]。

返回一个整数数组 ans，其中 ans[i] 等于子数组 nums[li...ri] 中出现至少 thresholdi 次的元素，选择频率最高的元素（如果有平局，则选择最小的），如果不存在这样的元素，则返回 -1。

示例 1：

输入：nums = [1,1,2,2,1,1], queries = [[0,5,4],[0,3,3],[2,3,2]]
输出：[1,-1,2]

示例 2：

输入：nums = [3,2,3,2,3,2,3], queries = [[0,6,4],[1,5,2],[2,4,1],[3,3,1]]
输出：[3,2,3,2]

约束条件：

1 <= nums.length == n <= 10^4
1 <= nums[i] <= 10^9
1 <= queries.length <= 5 * 10^4
queries[i] = [li, ri, thresholdi]
0 <= li <= ri < n
1 <= thresholdi <= ri - li + 1

解题思路

这道题要求在指定区间内找出频次达到阈值的最小元素。直接暴力对每个查询统计频次会超时，我们需要使用**Mo 算法（莫队算法）**进行优化。

Mo 算法是一种离线查询算法，适用于区间查询问题。核心思想是：

分块排序：以 √n 为块大小，将查询按 (l/√n, r) 排序
滑动窗口：维护当前区间 [L, R]，通过移动左右端点来处理各个查询
频次维护：使用哈希表记录元素频次，使用桶（bucket）按频次分组元素

具体实现：

用 cnt 记录每个元素的出现次数
用 bucket[f] 存储频次为 f 的所有元素集合
当区间端点移动时，动态更新 cnt 和 bucket
查询时从阈值开始向上扫描，找到满足条件的最小元素

时间复杂度优化关键在于排序后的查询序列能最小化区间端点的移动次数。

推荐解法：Mo 算法 + 桶分组

代码实现

class Solution {
public:
    vector<int> subarrayMajority(vector<int>& nums, vector<vector<int>>& queries) {
        int n = nums.size();
        int B = sqrt(n);
        int m = queries.size();
        
        vector<int> order(m);
        iota(order.begin(), order.end(), 0);
        
        sort(order.begin(), order.end(), [&](int i, int j) {
            int bi = queries[i][0] / B, bj = queries[j][0] / B;
            if (bi != bj) return bi < bj;
            return queries[i][1] < queries[j][1];
        });
        
        unordered_map<int, int> cnt;
        vector<set<int>> bucket(n + 1);
        vector<int> result(m);
        
        int L = 0, R = -1;
        
        for (int idx : order) {
            int l = queries[idx][0], r = queries[idx][1], threshold = queries[idx][2];
            
            while (R < r) {
                R++;
                int val = nums[R];
                if (cnt[val] > 0) bucket[cnt[val]].erase(val);
                cnt[val]++;
                bucket[cnt[val]].insert(val);
            }
            
            while (L > l) {
                L--;
                int val = nums[L];
                if (cnt[val] > 0) bucket[cnt[val]].erase(val);
                cnt[val]++;
                bucket[cnt[val]].insert(val);
            }
            
            while (R > r) {
                int val = nums[R];
                bucket[cnt[val]].erase(val);
                cnt[val]--;
                if (cnt[val] > 0) bucket[cnt[val]].insert(val);
                R--;
            }
            
            while (L < l) {
                int val = nums[L];
                bucket[cnt[val]].erase(val);
                cnt[val]--;
                if (cnt[val] > 0) bucket[cnt[val]].insert(val);
                L++;
            }
            
            int ans = -1;
            for (int f = threshold; f <= n; f++) {
                if (!bucket[f].empty()) {
                    ans = *bucket[f].begin();
                    break;
                }
            }
            result[idx] = ans;
        }
        
        return result;
    }
};

class Solution:
    def subarrayMajority(self, nums: List[int], queries: List[List[int]]) -> List[int]:
        from collections import defaultdict
        import math
        
        n = len(nums)
        B = int(math.sqrt(n))
        m = len(queries)
        
        order = list(range(m))
        order.sort(key=lambda i: (queries[i][0] // B, queries[i][1]))
        
        cnt = defaultdict(int)
        bucket = [set() for _ in range(n + 1)]
        result = [0] * m
        
        L, R = 0, -1
        
        for idx in order:
            l, r, threshold = queries[idx]
            
            while R < r:
                R += 1
                val = nums[R]
                if cnt[val] > 0:
                    bucket[cnt[val]].discard(val)
                cnt[val] += 1
                bucket[cnt[val]].add(val)
            
            while L > l:
                L -= 1
                val = nums[L]
                if cnt[val] > 0:
                    bucket[cnt[val]].discard(val)
                cnt[val] += 1
                bucket[cnt[val]].add(val)
            
            while R > r:
                val = nums[R]
                bucket[cnt[val]].discard(val)
                cnt[val] -= 1
                if cnt[val] > 0:
                    bucket[cnt[val]].add(val)
                R -= 1
            
            while L < l:
                val = nums[L]
                bucket[cnt[val]].discard(val)
                cnt[val] -= 1
                if cnt[val] > 0:
                    bucket[cnt[val]].add(val)
                L += 1
            
            ans = -1
            for f in range(threshold, n + 1):
                if bucket[f]:
                    ans = min(bucket[f])
                    break
            result[idx] = ans
        
        return result

public class Solution {
    public int[] SubarrayMajority(int[] nums, int[][] queries) {
        int n = nums.Length;
        int B = (int)Math.Sqrt(n);
        int m = queries.Length;
        
        var order = Enumerable.Range(0, m).ToArray();
        Array.Sort(order, (i, j) => {
            int bi = queries[i][0] / B, bj = queries[j][0] / B;
            if (bi != bj) return bi.CompareTo(bj);
            return queries[i][1].CompareTo(queries[j][1]);
        });
        
        var cnt = new Dictionary<int, int>();
        var bucket = new SortedSet<int>[n + 1];
        for (int i = 0; i <= n; i++) {
            bucket[i] = new SortedSet<int>();
        }
        var result = new int[m];
        
        int L = 0, R = -1;
        
        foreach (int idx in order) {
            int l = queries[idx][0], r = queries[idx][1], threshold = queries[idx][2];
            
            while (R < r) {
                R++;
                int val = nums[R];
                if (cnt.ContainsKey(val) && cnt[val] > 0) {
                    bucket[cnt[val]].Remove(val);
                }
                cnt[val] = cnt.GetValueOrDefault(val, 0) + 1;
                bucket[cnt[val]].Add(val);
            }
            
            while (L > l) {
                L--;
                int val = nums[L];
                if (cnt.ContainsKey(val) && cnt[val] > 0) {
                    bucket[cnt[val]].Remove(val);
                }
                cnt[val] = cnt.GetValueOrDefault(val, 0) + 1;
                bucket[cnt[val]].Add(val);
            }
            
            while (R > r) {
                int val = nums[R];
                bucket[cnt[val]].Remove(val);
                cnt[val]--;
                if (cnt[val] > 0) {
                    bucket[cnt[val]].Add(val);
                }
                R--;
            }
            
            while (L < l) {
                int val = nums[L];
                bucket[cnt[val]].Remove(val);
                cnt[val]--;
                if (cnt[val] > 0) {
                    bucket[cnt[val]].Add(val);
                }
                L++;
            }
            
            int ans = -1;
            for (int f = threshold; f <= n; f++) {
                if (bucket[f].Count > 0) {
                    ans = bucket[f].Min;
                    break;
                }
            }
            result[idx] = ans;
        }
        
        return result;
    }
}

var subarrayMajority = function(nums, queries) {
    const n = nums.length;
    const B = Math.floor(Math.sqrt(n));
    const m = queries.length;
    
    const order = Array.from({length: m}, (_, i) => i);
    order.sort((i, j) => {
        const bi = Math.floor(queries[i][0] / B);
        const bj = Math.floor(queries[j][0] / B);
        if (bi !== bj) return bi - bj;
        return queries[i][1] - queries[j][1];
    });
    
    const cnt = new Map();
    const bucket = Array.from({length: n + 1}, () => new Set());
    const result = new Array(m);
    
    let L = 0, R = -1;
    
    for (const idx of order) {
        const [l, r, threshold] = queries[idx];
        
        while (R < r) {
            R++;
            const val = nums[R];
            if (cnt.has(val) && cnt.get(val) > 0) {
                bucket[cnt.get(val)].delete(val);
            }
            cnt.set(val, (cnt.get(val) || 0) + 1);
            bucket[cnt.get(val)].add(val);
        }
        
        while (L > l) {
            L--;
            const val = nums[L];
            if (cnt.has(val) && cnt.get(val) > 0) {
                bucket[cnt.get(val)].delete(val);
            }
            cnt.set(val, (cnt.get(val) || 0) + 1);
            bucket[cnt.get(val)].add(val);
        }
        
        while (R > r) {
            const val = nums[R];
            bucket[cnt.get(val)].delete(val);
            cnt.set(val, cnt.get(val) - 1);
            if (cnt.get(val) > 0) {
                bucket[cnt.get(val)].add(val);
            }
            R--;
        }
        
        while (L < l) {
            const val = nums[L];
            bucket[cnt.get(val)].delete(val);
            cnt.set(val, cnt.get(val) - 1);
            if (cnt.get(val) > 0) {
                bucket[cnt.get(val)].add(val);
            }
            L++;
        }
        
        let ans = -1;
        for (let f = threshold; f <= n; f++) {
            if (bucket[f].size > 0) {
                ans = Math.min(...bucket[f]);
                break;
            }
        }
        result[idx] = ans;
    }
    
    return result;
};

在 LeetCode 上运行：力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型	Mo 算法解法
时间复杂度	O((n + m) × √n + m log m)
空间复杂度	O(n + m)

说明：

时间复杂度：查询排序 O(m log m)，Mo 算法移动端点总共 O((n + m) × √n)，每次查询扫描桶 O(n)
空间复杂度：频次哈希表 O(n)，桶数组 O(n²)，结果数组 O(m)

题目描述#

解题思路#

解题思路#

代码实现#

复杂度分析#

题目描述

解题思路

解题思路

代码实现

复杂度分析