力扣第 162 场双周赛第 4 题
题目
给你一个长度为 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]
解释：
| 查询 |
子数组 |
阈值 |
频率表 |
答案 |
| [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 <= 1041 <= nums[i] <= 1091 <= queries.length <= 5 * 104queries[i] = [li, ri, thresholdi]0 <= li <= ri < n1 <= thresholdi <= ri - li + 1
分析
#1
- 区间众数问题首先想到用莫队
- 转移时要维护 (频率,元素) 的有序集合
- 直接用 SortedList 会超时，可以用懒删除堆来维护
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
37
38
39
40
|
class Solution:
def subarrayMajority(self, nums: List[int], queries: List[List[int]]) -> List[int]:
def add(i):
a = nums[i]
ct[a] += 1
heappush(pq,(-ct[a],a))
def pop(i):
a = nums[i]
ct[a] -= 1
if ct[a]>0:
heappush(pq,(-ct[a],a))
n,m = len(nums),len(queries)
sq = isqrt(n*n//m)+1
ct = defaultdict(int)
pq = []
res = [-1]*m
Q = [(l,r,t,i) for i,(l,r,t) in enumerate(queries)]
Q.sort(key=lambda p:(p[0]//sq,p[1]//sq*(1 if p[0]//sq&1 else -1)))
l0,r0 = 1,0
for l,r,t,i in Q:
while l0>l:
l0 -= 1
add(l0)
while r0<r:
r0 += 1
add(r0)
while l0<l:
pop(l0)
l0 += 1
while r0>r:
pop(r0)
r0 -= 1
while ct[pq[0][1]]!=-pq[0][0]:
heappop(pq)
w,a = pq[0]
if -w>=t:
res[i] = a
return res
|
8017 ms
#2
还可以用回滚莫队优化掉 log
- 先分块，查询在块内直接暴力统计
- 查询按左端点所处块分组，组内按右端点排序
- 固定左端点的块 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