LeetCode-Go 题解：1157 Online Majority Element In Subarray 在线区间众数查询——摩尔投票与线段树的结合

LeetCode-Go 题解1157 Online Majority Element In Subarray 在线区间众数查询——摩尔投票与线段树的结合【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go本文围绕 LeetCode-Go 仓库中 1157. Online Majority Element In Subarray 题解文档 展开深入讲解如何用「摩尔投票 线段树 下标二分查找」实现一个支持任意区间在线众数查询的数据结构 MajorityChecker。读完本文你将掌握摩尔投票的区间可加性原理、线段树节点自定义合并逻辑的写法以及如何用位置索引表在 O(log n) 时间内核验候选元素的真实出现次数并可直接在 LeetCode-Go 仓库中运行对应的 Go 实现与测试用例。题目回顾与数据结构定义题目要求实现一个MajorityChecker类提供两个 APIMajorityChecker(int[] arr)用给定数组arr构造实例int query(int left, int right, int threshold)返回子数组arr[left..right]中出现次数至少为 threshold的元素若不存在这样的元素则返回-1。题目附带的关键约束见 README.md约束项取值范围数组长度1 arr.length 20000元素取值1 arr[i] 20000查询区间每次查询满足0 left right len(arr)阈值条件每次查询满足2 * threshold right - left 1查询次数最多10000次其中2 * threshold right - left 1是一条非常重要的隐含信息threshold 始终严格大于区间长度的一半。这意味着目标元素必然是区间内的严格众数若存在必唯一也正是在这种前提下摩尔投票Boyer-Moore Majority Vote算法才能正确工作——它只能保证找出出现次数超过一半的候选者而无法区分恰好一半的情形。为什么是摩尔投票 线段树原文档给出了明确的解题思路摩尔投票 线段树同时指出摩尔投票思想的出处可参考本仓库第 169 题 Majority Element其 Go 实现见 169. Majority Element.go 中的majorityElement函数。摩尔投票的可加性摩尔投票用两个变量candidate和count完成一次线性扫描candidate记录当前候选人count记录候选人累计未被抵消的票数。扫描过程中遇到相同元素则count遇到不同元素则将该元素与候选人两两抵消count--当count归零时更换候选人。扫描结束后candidate即为可能存在的众数。关键问题在于线段树把大区间拆成多个小区间每个小区间各自跑一遍摩尔投票再把小区间结果合并起来再投一次票得到的候选人与对整个大区间直接跑一遍摩尔投票是否一致答案是一致的。原因在于真正的众数总会在某个小区间内被选出来而其余小区间的投票结果只是充当中和角色——即元素两两配对出局。想通这一点就能确认摩尔投票具有可加性associativity因此天然适配线段树线段树的每个节点都代表一段连续区间的投票摘要逐层 pushUp 合并最终汇聚成大区间的投票结果。线段树节点的自定义合并传统线段树节点通常只存一个数值区间和、区间最大值等。本题中的线段树节点则存一个结构体segmentItem包含candidate与count两个字段见源码 1157. Online Majority Element In Subarray.gotype segmentItem struct { candidate int count int }每个节点的candidate/count表示该节点覆盖区间内摩尔投票的结果。初始化时每个叶子节点的candidate为自身元素值、count 1。自底向上 pushUp 时执行摩尔投票合并原文档给出的merge逻辑如下mc.merge func(i, j segmentItem) segmentItem { if i.candidate j.candidate { return segmentItem{candidate: i.candidate, count: i.count j.count} } if i.count j.count { return segmentItem{candidate: i.candidate, count: i.count - j.count} } return segmentItem{candidate: j.candidate, count: j.count - i.count} }务必注意这里的count并不是该元素在区间内出现的总次数而是摩尔投票中坚持到最后未被抵消的轮数。它只用于候选人的传递最终候选人的真实频次需要另行核验。Go 源码实现解析仓库中的完整实现位于 1157. Online Majority Element In Subarray.go结构如下。数据结构与构造函数type MajorityChecker struct { segmentTree []segmentItem data []int merge func(i, j segmentItem) segmentItem count map[int][]int }Constructor1157(arr)做三件事分配 4 倍数组长度的线段树数组4*len(arr)经典数组实现的空间安全上界定义上文所述的摩尔投票merge函数构造位置索引表countmap[int][]int记录每个元素在数组中出现的所有下标。由于遍历顺序就是下标递增顺序每个值对应的下标切片天然有序满足后续二分查找的前提源码 L21-L47。构建完成后调用buildSegmentTree(0, 0, len(arr)-1)递归建树叶子节点存{candidate: data[left], count: 1}内部节点通过merge合并左右孩子源码 L49-L59。区间查询query(left, right)递归进入线段树返回覆盖[left, right]区间的最小节点集合的合并结果若当前节点区间被查询区间完全覆盖直接返回该节点的segmentItem若查询区间完全落在左/右半边则单侧递归否则跨越中点将左右两半的查询结果用merge合并源码 L77-L90。线段树的区间查询复杂度为 O(log n)合并过程同样是摩尔投票因此查询得到的candidate即区间内可能存在也可能不存在的严格众数候选。用下标二分核验频次查询得到候选元素后还不能直接返回——需要验证它在该区间内是否真的出现至少threshold次。Query(left, right, threshold)利用位置索引表count完成核验源码 L93-L104start : sort.Search(len(mc.count[res.candidate]), func(i int) bool { return left mc.count[res.candidate][i] }) end : sort.Search(len(mc.count[res.candidate]), func(i int) bool { return right mc.count[res.candidate][i] }) - 1 if (end - start 1) threshold { return res.candidate } return -1两次sort.Search分别求出start第一个下标 ≥left的位置即区间的lowerBoundend第一个下标 right的位置减 1即区间的upperBound前驱。由于下标切片有序[start, end]之间全部是该元素在查询区间内的出现位置end - start 1即为真实出现次数。次数 ≥threshold则返回candidate否则返回-1。整体查询复杂度为 O(log n)线段树 O(log n)两次二分。举例arr [1,1,2,2,1,1]位置表为count map[1:[0 1 4 5] 2:[2 3]]。查询[0,5]内元素 1 的个数时lowerBound 0、upperBound 5区间[0,5]长度即 4与threshold比较即可判定。测试用例与运行验证仓库配套测试位于 1157. Online Majority Element In Subarray_test.go完整覆盖题目给出的示例arr : []int{1, 1, 2, 2, 1, 1} obj : Constructor1157(arr) obj.Query(0, 5, 4) // 1 obj.Query(0, 3, 3) // -1 obj.Query(2, 3, 2) // 2三个断言分别对应元素 1 在整个数组中出现 4 次满足阈值元素 1 在[0,3]中只出现 2 次不满足阈值 3元素 2 在[2,3]中出现 2 次满足阈值 2。测试还覆盖了空数组边界Constructor1157([]int{})后调用Query(0,0,1)必须返回-1对应源码中query对空数据的保护分支源码 L70-L75。在仓库根目录执行go test ./leetcode/1157.Online-Majority-Element-In-Subarray/...或按 gotest.sh 的方式对全量 leetcode 包生成覆盖率即可复现。构造函数中arr为空时会跳过建树保证后续查询安全返回-1。在 Segment Tree 专题中的定位仓库的线段树专题文档 ctl/template/Segment_Tree.md 将线段树用法划分为多类其中灵活构建线段树一节明确指出线段树节点可以存储多条信息合并两个节点的 pushUp 操作也可以是多样的并列举了第 850 题矩形面积 II与本 1157 题作为代表。这一点正是本题的精髓线段树并不局限于求和、最值等标量操作只要合并操作满足结合律associative就可以自定义节点负载与 pushUp 逻辑。摩尔投票的merge恰好具备该性质于是区间众数查询这一看似需要额外复杂结构的问题被优雅地降维为线段树维护投票摘要 位置表二分核验两个简单部件。总结核心组合摩尔投票解决候选者是谁线段树解决任意区间如何快速合并位置索引表 二分解决候选者出现多少次前提条件2 * threshold right - left 1保证查询目标必为严格众数这是摩尔投票正确性的前提实现要点count字段是未抵消票数而非出现次数最终判定必须依赖下标二分空数组需要边界保护复杂度建树 O(n)单次查询 O(log n)可支撑最多 10000 次查询可验证性源码与测试均位于 leetcode/1157.Online-Majority-Element-In-Subarray 目录可本地运行复现题目全部示例输出1、-1、2。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考