csp信奥赛C之摩尔投票算法详解原题说明洛谷P2397 yyy loves Maths VI (mode)/摩尔投票题目描述一共有n nn个正整数a i a_iai​需要找出其中的众数。特别提醒这个众数出现次数超过了一半。输入格式第一行一个整数n nn表示数的个数。第二行n nn个正整数a i a_iai​。输出格式一行一个整数表示众数。输入输出样例 1输入 15 2 3 3 3 3输出 13说明/提示【数据范围】对于100 % 100\%100%的数据1 ≤ n ≤ 2 × 10 6 1\le n \le 2\times 10^61≤n≤2×106a i ∈ [ 1 , 2 31 ) a_i \in [1,2^{31})ai​∈[1,231)。【内存限制】5MB思路分析题目要求在n nn个数中找出出现次数超过一半的众数且空间限制严格不能使用数组存储所有数。本题可以使用摩尔投票算法Boyer–Moore majority vote algorithm实现其核心思想是维护一个候选众数cand和一个计数器cnt初始cnt 0。遍历每个数若cnt 0将当前数设为候选众数计数器置为 1。否则若当前数等于候选众数计数器加 1否则计数器减 1。由于众数出现次数超过一半最终cand中保存的一定是众数。摩尔投票算法Boyer-Moore Majority Vote Algorithm实现原理详解摩尔投票算法是一种用于在线性时间和常数空间内寻找数组中出现次数超过一半的元素的算法。它由 Robert S. Boyer 和 J Strother Moore 于 1981 年提出特别适合内存受限的场景如本题。1. 算法核心思想“配对抵消”将数组中任意两个不同的元素视为一对“敌人”它们相互抵消删除。如果某个元素出现的次数超过总数的一半那么无论怎么抵消最后剩下的那个元素一定是该众数。更形象的理解想象你有一堆球每个球上标有一个数字。你随机拿出两个球如果数字不同就把它们都扔掉抵消如果数字相同就保留一个实际上相当于计数增加。重复这个过程最后剩下的球上的数字就是出现次数超过一半的众数。2. 算法步骤算法维护两个变量candidate当前候选的众数。count当前候选的“净支持数”即当前候选比其它数多出现的次数。遍历数组的每个元素x如果count 0说明之前的候选已经被完全抵消将x设为新的candidate并将count置为 1。否则如果x candidate说明当前元素与候选相同支持度增加count。否则x ! candidate说明当前元素与候选不同产生一次抵消count--。遍历结束后candidate中保存的就是可能的众数。由于题目保证众数存在且出现次数超过一半因此candidate一定是正确答案。3. 算法举例以输入2 3 3 3 3为例初始candidate 0,count 0读入2count 0→ 设candidate 2,count 1读入33 ! 2→ 抵消count--→count 0读入3count 0→ 设candidate 3,count 1读入33 3→count→count 2读入33 3→count→count 3输出candidate 3正确。4. 为什么算法正确我们需要证明如果存在一个元素出现次数超过一半那么遍历结束后candidate一定是该元素。证明思路设数组长度为n众数为m出现次数为k n/2。在遍历过程中每次遇到与candidate不同的元素时count减 1相当于将当前candidate与另一个不同元素配对抵消。由于m出现的次数超过一半它不可能被完全抵消最多只能和它不同的元素一一抵消。更严谨地考虑整个过程中抵消的总次数。每次抵消count减 1都会消耗一个非m元素和一个当前候选可能是m也可能不是。但无论当前候选是谁最终m的“净胜”次数至少为k - (n - k) 0所以当遍历结束时count必定大于 0 且candidate就是m。另一种数学证明定义“净票数”为当前候选的出现次数减去其他元素的出现次数。在遍历过程中每次遇到相同元素净票数 1遇到不同元素净票数 -1。由于众数的出现次数超过一半它的最终净票数一定为正因此最后剩下的候选必为众数。5. 算法特点时间复杂度O(n)只需一次遍历。空间复杂度O(1)仅用两个变量。局限性该算法只能用于确认存在且出现次数超过一半的元素。如果题目没有保证则需要在第一遍找出候选后再进行第二遍扫描验证该候选的出现次数是否真的超过一半。本题明确保证众数存在且超过一半因此无需验证。6. 为什么不能直接排序或哈希排序时间复杂度 O(n log n)且可能需额外空间如归并排序或改变原数组。哈希表空间复杂度 O(n)对于 n2×10^6 且内存限制严格的情况可能不可行。摩尔投票算法完美平衡了时间和空间是解决此类问题的最优方法。7. 总结摩尔投票算法通过巧妙的“配对抵消”策略在只遍历一次且几乎不占用额外内存的情况下找出了出现次数超过一半的元素。它的实现简单逻辑清晰是算法竞赛和面试中的经典问题。AC代码#includebits/stdc.husingnamespacestd;intn;// 数字个数intmain(){cinn;// 输入个数intcand0,cnt0;// cand当前候选众数cnt当前候选的“净支持数”for(inti1;in;i){intx;cinx;// 读入一个数if(cnt0){// 若计数器为0则当前数成为新的候选众数candx;cnt1;}elseif(xcand){// 若当前数等于候选众数支持度1cnt;}else{// 否则支持度-1cnt--;}}coutcandendl;// 最终cand一定是众数题目保证存在且超过一半return0;}【文末福利一等奖秘籍汇总】完整csp信奥赛C学习资料1、csp/信奥赛C完整信奥赛系列课程永久学习https://edu.csdn.net/lecturer/7901 点击跳转2、CSP信奥赛C竞赛拿奖视频课https://edu.csdn.net/course/detail/40437 点击跳转3、csp信奥赛高频考点知识详解及案例实践CSP信奥赛C动态规划https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转CSP信奥赛C标准模板库STLhttps://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转信奥赛C提高组csp-s知识详解及案例实践https://blog.csdn.net/weixin_66461496/category_13113932.html 点击跳转4、csp信奥赛冲刺一等奖有效刷题题解CSP信奥赛C初赛及复赛高频考点真题解析持续更新https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转信奥赛C提高组csp-s初赛复赛真题题解持续更新https://blog.csdn.net/weixin_66461496/category_13125089.html 点击跳转5、GESP C考级真题题解GESP(C 一级二级三级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转GESP(C 四级五级六级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转GESP(C 七级八级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_13117178.html 点击跳转· 文末祝福 ·#includebits/stdc.husingnamespacestd;intmain(){cout跟着王老师一起学习信奥赛C;cout 成就更好的自己 ;cout csp信奥赛一等奖属于你! ;return0;}