3636：查询超过阈值频率最高元素（2451 分）

Ian

2025-08-02 约 591 字预计阅读 2 分钟次阅读

力扣第 162 场双周赛第 4 题

题目

给你一个长度为 n 的整数数组 nums 和一个查询数组 queries，其中 queries[i] = [l_i, r_i, threshold_i]。

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

示例 1:

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

输出： [1,-1,2]

解释：

查询	子数组	阈值	频率表	答案
[0, 5, 4]	[1, 1, 2, 2, 1, 1]	4	1 → 4, 2 → 2	1
[0, 3, 3]	[1, 1, 2, 2]	3	1 → 2, 2 → 2	-1
[2, 3, 2]	[2, 2]	2	2 → 2	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]

解释：

查询	子数组	阈值	频率表	答案
[0, 6, 4]	[3, 2, 3, 2, 3, 2, 3]	4	3 → 4, 2 → 3	3
[1, 5, 2]	[2, 3, 2, 3, 2]	2	2 → 3, 3 → 2	2
[2, 4, 1]	[3, 2, 3]	1	3 → 2, 2 → 1	3
[3, 3, 1]	[2]	1	2 → 1	2

提示：

1 <= nums.length == n <= 10⁴
1 <= nums[i] <= 10⁹
1 <= queries.length <= 5 * 10⁴
queries[i] = [l_i, r_i, threshold_i]
0 <= l_i <= r_i < n
1 <= threshold_i <= r_i - l_i + 1

分析

采用回滚莫队

先分块，查询在块内直接暴力统计
查询按左端点所处块分组，组内按右端点排序
固定左端点的块 a，遍历右端点可以统计 a 右边的部分
属于块 a 的部分每次统计后再撤销，即回滚

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36


class Solution:
    def subarrayMajority(self, nums: List[int], queries: List[List[int]]) -> List[int]:
        n,m = len(nums),len(queries)
        sq = isqrt(n*n//m)+1
        N = (n-1)//sq+1
        res = [-1]*m
        d = defaultdict(list)
        for i,(l,r,t) in enumerate(queries):
            a,b = l//sq,r//sq
            if a==b:
                ans = min([(-w,c) for c,w in Counter(nums[l:r+1]).items()])
                if -ans[0]>=t:
                    res[i] = ans[1]
            else:
                d[a].append((r,l,t,i))
        for a in d:
            ans = (0,-1)
            ct = defaultdict(int)
            l0 = r0 = a*sq+sq
            for r,l,t,i in sorted(d[a]):
                for j in range(r0,r+1):
                    x = nums[j]
                    ct[x] += 1
                    ans = min(ans,(-ct[x],x))
                tmp = ans
                for j in range(l,l0):
                    x = nums[j]
                    ct[x] += 1
                    ans = min(ans,(-ct[x],x))
                if -ans[0]>=t:
                    res[i] = ans[1]
                ans = tmp
                for j in range(l,l0):
                    ct[nums[j]] -= 1
                r0 = r+1
        return res

2927 ms

目录

3636：查询超过阈值频率最高元素（2451 分）

题目

分析

解答