大家好，我是你们的算法小伙伴。今天我们来练习一道经典的数组问题 ——LeetCode 169. 多数元素，它的最优解法「摩尔投票法」非常巧妙，是面试中的高频考点。
题目描述
给定一个大小为n的数组nums，返回其中的多数元素。多数元素是指在数组中出现次数大于⌊ n/2 ⌋的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
示例 1：
输入：nums = [3,2,3] 输出：3示例 2：
输入：nums = [2,2,1,1,1,2,2] 输出：2提示：
n == nums.length1 <= n <= 5 * 10^4-10^9 <= nums[i] <= 10^9- 输入保证数组中一定有一个多数元素
进阶：尝试设计时间复杂度为 O (n)、空间复杂度为 O (1) 的算法解决此问题。
解题思路
方法一：哈希表统计（直观但空间复杂度高）
遍历数组，用哈希表记录每个元素的出现次数，最后遍历哈希表找到出现次数大于 n/2 的元素。
- 时间复杂度：O (n)
- 空间复杂度：O (n)
方法二：排序取中间元素（利用多数元素特性）
因为多数元素出现次数大于 n/2，所以排序后数组中间位置的元素一定是多数元素。
- 时间复杂度：O (n log n)
- 空间复杂度：O (1)（若使用原地排序）
方法三：摩尔投票法（最优解）
这是题目进阶要求的 O (n) 时间、O (1) 空间解法，核心思想是抵消不同元素，也是我们重点要讲解的方法。
核心前提
题目明确保证：数组中一定存在多数元素，且出现次数 > n/2。这意味着：多数元素的数量 > 所有其他元素的数量之和，这是摩尔投票法能生效的根本 —— 它的 “票数” 永远无法被完全抵消。
通俗类比理解
我们可以把这个过程想象成一场 “候选人对抗赛”：
- 数组里的每个元素都是一个 “候选人”，互相 “投票对抗”；
- 多数元素的支持者足够多，哪怕和所有其他候选人对抗，最后剩下的也一定是它；
count就是当前候选者的净胜票数：- 遇到和自己一样的元素 → 净胜票 + 1（支持者增加）；
- 遇到不一样的元素 → 净胜票 - 1（互相抵消）；
- 净胜票为 0 时 → 说明当前候选者的票数被完全抵消，换当前元素当新候选。
算法步骤
- 初始化：选数组第一个元素为初始候选
candidate，计数器count = 1； - 从第二个元素开始遍历数组：
- 若当前元素等于
candidate→count++； - 若当前元素不等于
candidate→count--； - 若
count == 0→ 更新candidate为当前元素，重置count = 1；
- 若当前元素等于
- 遍历结束后，
candidate就是多数元素。
代码实现
class Solution { public int majorityElement(int[] nums) { // 1. 初始化：选第一个元素当初始候选，初始净胜票为 1 int candidate = nums[0]; int count = 1; // 2. 从第二个元素开始遍历（第一个已作为候选） for (int i = 1; i < nums.length; i++) { if (nums[i] == candidate) { // 情况1：遇到和候选相同的元素 → 净胜票+1 count++; } else { // 情况2：遇到不同元素 → 净胜票-1（互相抵消） count--; // 情况3：净胜票为 0 → 候选者被完全抵消，换当前元素当新候选 if (count == 0) { candidate = nums[i]; count = 1; } } } // 3. 遍历结束，剩下的候选就是多数元素 return candidate; } }代码逐行拆解
- 初始化：
candidate = nums[0]先假设第一个元素是候选，count = 1表示它有 1 票领先； - 遍历逻辑：
- 相同元素：增强当前候选的领先优势；
- 不同元素：消耗当前候选的票数，实现 “抵消”；
- 票数清零：说明当前候选的优势耗尽，更换新候选重新开始计数；
- 结果保证：因为多数元素数量 > 其他元素总和，所以它永远无法被完全抵消，最终一定会成为最后剩下的候选。
实例模拟验证
我们以nums = [2,2,1,1,1,2,2]（多数元素是 2，出现 4 次，n=7，4>3.5）为例，全程模拟执行过程：
表格
| 遍历位置 (i) | 当前元素 | candidate (候选) | count (净胜票) | 执行逻辑 |
|---|---|---|---|---|
| 初始化 | - | 2 | 1 | 选第一个元素 2 当候选，初始票 1 |
| i=1 | 2 | 2 | 2 | 和候选相同，净胜票 + 1 |
| i=2 | 1 | 2 | 1 | 和候选不同，净胜票 - 1（抵消 1 票） |
| i=3 | 1 | 2 | 0 | 和候选不同，净胜票 - 1 → 变为 0 |
| i=4 | 1 | 1 | 1 | count=0 → 换候选为 1，重置票 1 |
| i=5 | 2 | 1 | 0 | 和候选不同，净胜票 - 1 → 变为 0 |
| i=6 | 2 | 2 | 1 | count=0 → 换候选为 2，重置票 1 |
| 遍历结束 | - | 2 | 1 | 返回候选 2（正确结果） |
复杂度分析
- 时间复杂度：O (n)。仅需遍历数组一次，执行 n-1 次操作。
- 空间复杂度：O (1)。仅使用两个变量存储候选和计数器，无额外空间开销。
总结
这道题的核心魅力在于摩尔投票法，它完美利用了「多数元素出现次数超过一半」的特性，在不借助额外空间的情况下，通过简单的计数与抵消操作高效找到结果。
这种思想在处理「寻找出现次数超过 1/k 的元素」等进阶问题时也有重要应用，是算法面试中必须掌握的经典技巧。
今天的每日算法练习就到这里，我们明天再见！👋
