1157：子数组中占绝大多数的元素（2205 分）

力扣第 149 场周赛第 4 题

题目

设计一个数据结构，有效地找到给定子数组的 多数元素 。

子数组的 多数元素 是在子数组中出现 threshold 次数或次数以上的元素。

实现 MajorityChecker 类:

• MajorityChecker(int[] arr) 会用给定的数组 arr 对 MajorityChecker 初始化。
• int query(int left, int right, int threshold) 返回子数组中的元素 arr[left...right] 至少出现 threshold 次数，如果不存在这样的元素则返回 -1。

示例 1：

输入:
["MajorityChecker", "query", "query", "query"]
[[[1, 1, 2, 2, 1, 1]], [0, 5, 4], [0, 3, 3], [2, 3, 2]]
输出：
[null, 1, -1, 2]

解释：
MajorityChecker majorityChecker = new MajorityChecker([1,1,2,2,1,1]);
majorityChecker.query(0,5,4); // 返回 1
majorityChecker.query(0,3,3); // 返回 -1
majorityChecker.query(2,3,2); // 返回 2

提示：

• 1 <= arr.length <= 2 * 104
• 1 <= arr[i] <= 2 * 104
• 0 <= left <= right < arr.length
• threshold <= right - left + 1
• 2 * threshold > right - left + 1
• 调用 query 的次数最多为 104

分析

区间查询相关的常用算法有块状数组、树状数组、线段树等。本题的数据规模可以尝试块状数组的思想：

• threshold 小的查询，区间也小，暴力统计即可
• threshold 大的查询，数组中频数较大的元素也少，考虑直接从这些元素中找

具体实现时：

• 提前记录所有频数 >=100 的元素，及其在数组中的下标列表
• 查询时，假如 threshold<=100，则区间长度<=200，遍历即可
• 否则，遍历所有频数>=100 的元素，并在对应的下标列表中二分查找区间的边界，即可得到该元素在区间内出现的次数，判断是否符合即可
• 数组长度最多 2 * 10^4，频数>=100的元素最多200个，因此单次查询时间 O(200 logN)。

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

class MajorityChecker:

    def __init__(self, arr: List[int]):
        self.d = defaultdict(list)
        for i,x in enumerate(arr):
            self.d[x].append(i)
        self.cand = [x for x in self.d if len(self.d[x])>100]
        self.arr = arr
        
    def query(self, left: int, right: int, threshold: int) -> int:
        if threshold<=100:
            ct = Counter(self.arr[i] for i in range(left, right+1))
            x, w = ct.most_common(1)[0]
            return x if w>=threshold else -1
        for x in self.cand:
            w = bisect_right(self.d[x],right)-bisect_left(self.d[x],left) 
            if w>=threshold:
                return x
        return -1

392 ms