核心解题思路这道题是静态区间众数查询问题要求找出区间内出现次数 ≥ threshold 且频率最高的最小元素。最优解分块预处理 位置列表二分· 将数组分成大小为 √n 的块· 预处理 pmx[i][j]块 i 到块 j 的众数频率最高· 查询时区间 左零散部分 中间完整块 右零散部分· 候选众数 中间块的众数 左右零散部分所有元素· 用位置列表 二分查找统计每个候选在区间内的实际频率Python3 实现1. 方案一分块最优解pythonfrom typing import Listfrom collections import defaultdictimport mathimport bisectclass Solution:def subarrayMajority(self, nums: List[int], queries: List[List[int]]) - List[int]:n len(nums)size int(math.sqrt(n)) 1block_cnt (n size - 1) // size# 1. 预处理每个元素的所有出现位置pos defaultdict(list)for i, num in enumerate(nums):pos[num].append(i)# 2. 预处理块间众数 pmx[i][j]pmx [[0] * block_cnt for _ in range(block_cnt)]for i in range(block_cnt):cnt {}mode 0max_cnt 0for j in range(i, block_cnt):start j * sizeend min((j 1) * size, n)for k in range(start, end):num nums[k]c cnt.get(num, 0) 1cnt[num] cif c max_cnt or (c max_cnt and num mode):max_cnt cmode numpmx[i][j] mode# 辅助函数二分查找区间 [l, r] 内 x 的出现次数def count_freq(x: int, l: int, r: int) - int:if x not in pos:return 0lst pos[x]left bisect.bisect_left(lst, l)right bisect.bisect_right(lst, r)return right - left# 3. 处理每个查询ans []for l, r, threshold in queries:lb l // sizerb r // size# 同一块或相邻块直接暴力统计if lb rb or lb 1 rb:cnt {}mode 0max_cnt 0for i in range(l, r 1):num nums[i]c cnt.get(num, 0) 1cnt[num] cif c max_cnt or (c max_cnt and num mode):max_cnt cmode numans.append(mode if max_cnt threshold else -1)continue# 候选众数中间块的众数 左右零散部分的所有元素candidates set()candidates.add(pmx[lb 1][rb - 1]) # 中间完整块的众数# 左零散部分 [l, (lb1)*size - 1]for i in range(l, (lb 1) * size):candidates.add(nums[i])# 右零散部分 [rb*size, r]for i in range(rb * size, r 1):candidates.add(nums[i])# 统计每个候选的频率best_num -1best_freq 0for num in candidates:freq count_freq(num, l, r)if freq threshold:if freq best_freq or (freq best_freq and num best_num):best_freq freqbest_num numans.append(best_num)return ans2. 方案二位置列表 遍历所有元素简单版适合数据小pythonfrom typing import Listfrom collections import defaultdictimport bisectclass Solution:def subarrayMajority(self, nums: List[int], queries: List[List[int]]) - List[int]:# 预处理每个元素的所有出现位置pos defaultdict(list)for i, num in enumerate(nums):pos[num].append(i)ans []for l, r, threshold in queries:best_num -1best_freq 0# 遍历所有不同元素for num, lst in pos.items():left bisect.bisect_left(lst, l)right bisect.bisect_right(lst, r)freq right - leftif freq threshold:if freq best_freq or (freq best_freq and num best_num):best_freq freqbest_num numans.append(best_num)return ans3. 方案三Randomized随机化适合大数据快速近似pythonfrom typing import Listfrom collections import defaultdictimport bisectimport randomclass Solution:def subarrayMajority(self, nums: List[int], queries: List[List[int]]) - List[int]:n len(nums)pos defaultdict(list)for i, num in enumerate(nums):pos[num].append(i)# 频繁出现的元素大概率是众数# 随机抽样 20 次每次从区间随机选一个元素作为候选def count_freq(x, l, r):if x not in pos:return 0lst pos[x]return bisect.bisect_right(lst, r) - bisect.bisect_left(lst, l)ans []for l, r, threshold in queries:best_num -1best_freq 0# 随机抽样 30 次for _ in range(30):idx random.randint(l, r)num nums[idx]freq count_freq(num, l, r)if freq threshold:if freq best_freq or (freq best_freq and num best_num):best_freq freqbest_num numans.append(best_num)return ans复杂度分析方案 预处理时间 单次查询时间 空间分块 O(n√n) O(√n log n) O(n √n²) O(n)简单版 O(n) O(U log n) O(n)随机化 O(n) O(30 log n) O(n)关键要点1. 分块思想平衡预处理和查询的复杂度2. 位置列表 二分快速统计任意元素在区间内的出现次数3. 候选众数优化只需检查中间块众数 边界元素大大减少候选数量4. 阈值过滤频率 threshold 的元素直接跳过测试示例python# 示例nums [1, 3, 2, 3, 3, 2, 2, 1]queries [[0, 7, 3], [0, 4, 2], [1, 5, 3]]sol Solution()print(sol.subarrayMajority(nums, queries)) # 输出: [2, 3, -1]