LeetCode 169 多数元素（Majority Element）题解：摩尔投票法（水王问题）O(N) 时间 O(1) 空间

LeetCode 169 多数元素Majority Element题解摩尔投票法水王问题O(N) 时间 O(1) 空间【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode本文是 LeetCode 题解仓库中 169. 多数元素 一题的完整技术解读。题目要求在线性时间内找出数组中出现次数超过 ⌊n/2⌋ 的多数元素本仓库给出的核心解法是经典的摩尔投票法Boyer–Moore Majority Vote Algorithm又称水王问题解法。读完本文你将掌握投票算法的配对消除原理、正确性证明以及 JS / Python / C / Java 四种语言的实现并了解如何将其推广到出现超过 n/k 次的通用场景。题目描述与数据约束原题描述如下给定一个大小为 n 的数组找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊n/2⌋ 的元素。你可以假设数组是非空的并且给定的数组总是存在多数元素。示例示例 1: 输入: [3,2,3] 输出: 3 示例 2: 输入: [2,2,1,1,1,2,2] 输出: 2这里有一个非常重要的前提条件题目保证数组非空且一定存在多数元素。这并非可有可无的假设而是摩尔投票法能够直接返回候选值而无需二次校验的根本前提后文会详细说明。本仓库将本题收录于 简单难度题目合集 与 SUMMARY.md 总目录属于入门级高频面试题原题解文档还记录了该题在阿里、腾讯、百度、字节、Adobe、Zenefits 等公司的面试中出现记录。前置知识从水王问题到摩尔投票法这道题在业界有一个更著名的别名——水王问题Water King Problem即在一个序列中找出出现次数超过总数一半的元素。原文档将其列为前置知识并明确思路章节的标题就是投票算法。直觉解法哈希计数最符合直觉的做法是利用额外的哈希表Map/Dictionary记录每个元素出现的次数同时用一个单独变量记录当前出现次数最多的元素。这种做法的时间复杂度为 O(N)但空间复杂度为 O(N)在 N 很大时内存开销明显。// 直觉解法空间 O(N)仅供对比非本仓库推荐 var majorityElementByMap function (nums) { const count new Map(); let majority nums[0]; for (const num of nums) { count.set(num, (count.get(num) || 0) 1); if (count.get(num) count.get(majority)) majority num; } return majority; };投票算法的核心思想原文档给出的核心思路是通过不断消除不同元素直到没有不同元素剩下的元素就是我们要找的元素。注意这里的关键是消除不同的数。背后的原理非常简单最坏情况下非众数中的每一个数都分别与一个众数进行配对消除那么最终剩下的必然是众数其他情况下显然剩下的也是众数本身。这个一票对一票、不同则抵消的过程就是摩尔投票法。从源码结构看仓库为本题单独维护了一份可视化图源 169.majority-element.drawio并在 assets/problems 下存放了本题的推导示意图展示的正是拇指向上保留候选/ 拇指向下消除配对的配对消除全过程。图中以示例[2,2,1,1,1,2,2]演示保留的候选元素 2 依次与 2、1、2 配对后最终剩余 2被消除的一侧中1 与 1、2 配对后完全被消除。同时图示还标注了关键推导公式若多数元素出现次数为 m总元素个数为 N则经过两两配对抵消后多数元素最终剩余数量为m - (N - m) 2m - N。只要满足m N/2即2m - N 0最终必然有非零数量的多数元素存活这正是算法正确性的数学依据。摩尔投票法的关键点解析原文档将投票算法列为关键点。实现时需要注意以下三个细节初始化候选元素majority取数组首元素计数count从 1 开始首元素自占一票遍历从下标 1 开始计零换将当count归零时说明当前候选已与其前方所有元素完全抵消此时把当前遍历到的元素设为新候选并重置计数同增异减当前元素与候选相同则count不同则count--本质是两个不同元素相互抵消的抽象。四种语言实现仓库原版代码原文档声明语言支持 JS、Python、CPP、Java以下为仓库原文代码JavaScriptvar majorityElement function (nums) { let count 1; let majority nums[0]; for (let i 1; i nums.length; i) { if (count 0) { majority nums[i]; } if (nums[i] majority) { count; } else { count--; } } return majority; };Pythonclass Solution: def majorityElement(self, nums: List[int]) - int: count, majority 1, nums[0] for num in nums[1:]: if count 0: majority num if num majority: count 1 else: count - 1 return majorityCclass Solution { public: int majorityElement(vectorint nums) { int ans 0, cnt 0; for (int n : nums) { if (ans n) cnt; else if (cnt 0) --cnt; else { ans n; cnt 1; } } return ans; } };C 版本与 JS/Python 的写法略有差异但等价ans n时计数加一cnt 0且元素不同时计数减一只有当计数已经为 0 时才更换候选。该版本无需单独初始化首元素从第一个元素起cnt 0即落入else分支完成初始化。Javaclass Solution { public int majorityElement(int[] nums) { int count 0; Integer candidate null; for (int num : nums) { if (count 0) { candidate num; } count (num candidate) ? 1 : -1; } return candidate; } }Java 版本使用Integer candidate null以在count 0时更新候选并通过三元表达式把同增异减合并成一条语句是四种实现中最简洁的写法。复杂度分析原文档给出的复杂度结论如下时间复杂度O(N)其中 N 为数组长度。整个算法只对数组做一次线性扫描每步操作均为 O(1)空间复杂度O(1)只使用常量个额外变量候选元素与计数器不随输入规模增长。这也是摩尔投票法相对哈希计数解法的核心优势在保持 O(N) 时间的同时把空间压到 O(1)完全满足题目设计 O(1) 空间算法的进阶诉求。边界情况与正确性前提数组长度为 1如输入[1]JS 版本循环体不执行直接返回nums[0]正确多数元素在首元素如[2,2,1,1,1,2,2]候选始终是 2计数在 0 与 1 之间摆动但永不提前换将最终返回 2前提约束题目已保证数组总是存在多数元素因此投票结束后返回的候选无需再做一次全数组扫描校验。若去掉该前提则需要在投票结束后额外遍历一次统计候选的真实出现次数确认是否大于 ⌊n/2⌋这一点在图解中也有明确标注——没有该约束投票算法就会失效。延伸阅读从超过 1/2推广到超过 1/k仓库中与本主题强相关的姊妹题是 229. 求众数 II。该题要求找出所有出现次数超过 ⌊n/3⌋ 的元素最多可能有两个答案。其解法正是 169 题摩尔投票法的一对多推广同时维护两个候选与两个计数器因为超过 1/3 的元素至多两个遍历规则变为命中候选 1 或候选 2 则对应计数加一计数为 0 的位置可直接让位给新元素否则两个计数同时减一三元素配对抵消由于最终存活的两个候选只是出现次数最多的前两名不一定都满足大于 n/3因此最后必须重新扫描数组统计两个候选的真实频次并过滤例如 C 实现末尾if (c1 nums.size() / 3)的二次校验。进一步推广若题目把阈值从 3 改成 k则需要维护 k-1 个候选与 k-1 个计数器思路完全一致。229 题解文档末尾也为此留下了3 变成 k 怎么解决的扩展思考题。如何在仓库中定位与学习本题题解主文档problems/169.majority-element.md中文、problems/169.majority-element.en.md英文难度归档简单难度题目合集、英文合集 collections/easy.en.md总目录入口SUMMARY.md 第 69 行图解资源assets/problems/169.majority-element.png、可编辑图源 assets/drawio/169.majority-element.drawio姊妹题延伸229. 求众数 II。摩尔投票法作为用 O(1) 空间解决众数问题的经典范式不仅是 169/229 两题的通用解法也是面试中考察候选人能否从哈希表直觉走向数学优化的代表性题目。掌握其配对消除的推导过程即可一通百通。【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考