1. 解题思路
这一题我其实没想到什么好的思路，只能是最暴力地尝试了一下分段树，倒是勉强搞定了……
关于分段树的相关内容，网上其实比较多，我自己也有一篇水文《经典算法：Segment Tree》作为备忘，唯一的区别就是聚合算法上面这里采用的是counter的合并，这个其实不是很优雅，还是挺费事费力的，不过能搞定就行……
2. 代码实现
给出python代码实现如下：
class SegmentTree:
def __init__(self, arr):
self.length = len(arr)
self.tree = self.build(arr)
def feature_func(self, *args):
cnt = defaultdict(int)
for _cnt in args:
for k, v in _cnt.items():
cnt[k] += v
return cnt
def build(self, arr):
n = len(arr)
tree = [0 for _ in range(2*n)]
for i in range(n):
tree[i+n] = {arr[i]: 1}
for i in range(n-1, 0, -1):
tree[i] = self.feature_func(tree[i<<1], tree[(i<<1) | 1])
return tree
def update(self, idx, val):
idx = idx + self.length
self.tree[idx] = {val:1}
while idx > 1:
self.tree[idx>>1] = self.feature_func(self.tree[idx], self.tree[idx ^ 1])
idx = idx>>1
return
def query(self, lb, rb):
lb += self.length
rb += self.length
nodes = []
while lb < rb:
if lb & 1 == 1:
nodes.append(self.tree[lb])
lb += 1
if rb & 1 == 0:
nodes.append(self.tree[rb])
rb -= 1
lb = lb >> 1
rb = rb >> 1
if lb == rb:
nodes.append(self.tree[rb])
return self.feature_func(*nodes)
class Solution:
def subarrayMajority(self, nums: List[int], queries: List[List[int]]) -> List[int]:
segment_tree = SegmentTree(nums)
def query(l, r, thres):
cnt = segment_tree.query(l, r)
valid = [(k, v) for k, v in cnt.items() if v >= thres]
if valid == []:
return -1
max_freq = max(v for k, v in valid)
return min(k for k, v in valid if v == max_freq)
return [query(l, r, thres) for l, r, thres in queries]
提交代码评测得到：耗时9933ms，占用内存42.30MB。