LeetCode 169. 多数元素
题目核心
给定一个大小为 n 的数组 nums，返回其中出现次数 超过一半 的元素。
多数元素是指数组中出现次数大于 n/2 的元素。题目保证数组中一定存在多数元素。
例如：
nums = [3, 2, 3]
答案：3nums = [2, 2, 1, 1, 1, 2, 2]
答案：2解题思考过程
第一步：理解问题
题目说"出现次数超过一半"，也就是说多数元素的数量比其他所有元素加起来还多。
这是一个关键条件！意味着如果我们用某种方式"抵消"不同的元素，最后剩下的一定是多数元素。
第二步：暴力解法（哈希表统计）
最直接的思路：用哈希表统计每个元素出现的次数，然后遍历哈希表找出现次数超过一半的元素。
时间复杂度：O(n)
空间复杂度：O(n)这个思路可行，但需要额外的哈希表空间。题目有没有要求 O(1) 空间？虽然题目没明确说，但我们应该追求最优解。
第三步：思考如何优化空间
能不能不用额外空间？
想到排序：排序后，中间位置的元素一定是多数元素（因为它出现超过一半）。
nums = [2, 2, 1, 1, 1, 2, 2]
排序后：[1, 1, 1, 2, 2, 2, 2]
中间位置：索引3，元素是2 ✓时间复杂度：O(n log n) - 排序的时间
空间复杂度：O(1) 或 O(n) - 取决于排序算法是否原地排序这个方法空间是O(1)了，但时间变成了O(n log n)，能不能更快？
第四步：想到摩尔投票法
题目说多数元素出现超过一半，这意味着：
多数元素的数量 > 其他所有元素数量之和如果我们把数组想象成：多数元素是"好人"，其他元素是"坏人"，每个人都要打架。
规则：
- 好人遇到坏人，同归于尽（抵消）
- 好人遇到好人，组队（计数+1）
- 坏人遇到坏人，组队（计数+1，但最后会被好人消灭）
因为好人数量 > 坏人数量之和，所以最后剩下的一定是好人！这就是摩尔投票法的核心思想：
- 维护一个候选人和计数器
- 遍历数组：
- 如果计数器为0，当前元素成为候选人
- 如果当前元素等于候选人，计数器+1
- 如果当前元素不等于候选人，计数器-1
第五步：验证摩尔投票法
以 [2, 2, 1, 1, 1, 2, 2] 为例：
初始化：candidate=null, count=0
i=0, val=2: count=0, candidate=2, count=1
i=1, val=2: 等于candidate, count=2
i=2, val=1: 不等于candidate, count=1
i=3, val=1: 不等于candidate, count=0
i=4, val=1: count=0, candidate=1, count=1
i=5, val=2: 不等于candidate, count=0
i=6, val=2: count=0, candidate=2, count=1
最后 candidate=2，正确！再试一个例子 [3, 2, 3]：
i=0, val=3: count=0, candidate=3, count=1
i=1, val=2: 不等于candidate, count=0
i=2, val=3: count=0, candidate=3, count=1
最后 candidate=3，正确！第六步：为什么这种方法能工作
因为多数元素出现次数超过一半，所以无论怎么抵消，最后剩下的一定是多数元素。
即使中间候选人被替换（如上面例子中i=4时candidate变成1），但最后还是会被多数元素"赢"回来。
时间复杂度：O(n)
空间复杂度：O(1)这是最优解法！
当前解法：摩尔投票法
当前代码使用的是摩尔投票法（Boyer-Moore Voting Algorithm），这是本题最优解法。
var majorityElement = function (nums) {
let length = nums.length;
let res = 0;
let index = nums[0];
for (let i = 0; i < length; i++) {
if (res == 0) {
index = nums[i];
}
if (nums[i] != index) {
res--;
} else {
res++;
}
}
return index;
};算法思想
摩尔投票法的核心思路是：
遇到相同的元素，投票数 +1
遇到不同的元素，投票数 -1
当投票数为 0 时，更换候选元素因为多数元素出现次数超过一半，所以它总能在投票中"战胜"其他所有元素。
为什么这样能找到多数元素
假设多数元素出现次数为 m，其他元素总次数为 n - m。
由于题目保证 m > n/2，所以：
m > n - m
m + m > n即使每次遇到多数元素都和其他元素"抵消"一次，多数元素也至少会剩下 m - (n - m) = 2m - n > 0 次。
因此最终剩下的候选元素一定是多数元素。
投票过程示例
以 nums = [2, 2, 1, 1, 1, 2, 2] 为例：
i=0: nums[0]=2, res=0 → index=2, res=1
i=1: nums[1]=2, res=1 → res=2
i=2: nums[2]=1, res=2 → res=1
i=3: nums[3]=1, res=1 → res=0
i=4: nums[4]=1, res=0 → index=1, res=1
i=5: nums[5]=2, res=1 → res=0
i=6: nums[6]=2, res=0 → index=2, res=1
最终 index=2，即答案为 2虽然中间候选元素会变化，但多数元素最终会赢到最后。
复杂度
- 时间复杂度：
O(n)，只需要遍历数组一次。 - 空间复杂度：
O(1)，只使用了常数级别的额外空间。
这是本题最优的时间和空间复杂度。
为什么不需要验证结果
题目保证数组中一定存在多数元素，所以摩尔投票法结束后得到的候选元素一定是答案。
如果题目不保证存在多数元素，则需要额外遍历一次数组，验证候选元素是否真的出现超过 n/2 次。
替代解法一：哈希表统计
可以用哈希表记录每个元素的出现次数，然后找到次数超过一半的元素。
var majorityElement = function (nums) {
const count = {};
const n = nums.length;
for (const num of nums) {
count[num] = (count[num] || 0) + 1;
if (count[num] > n / 2) {
return num;
}
}
return -1;
};- 时间复杂度：
O(n) - 空间复杂度：
O(n)，最坏情况下需要存储所有不同元素。
替代解法二：排序
因为多数元素出现次数超过一半，排序后数组中间位置的元素一定是多数元素。
var majorityElement = function (nums) {
nums.sort((a, b) => a - b);
return nums[Math.floor(nums.length / 2)];
};- 时间复杂度：
O(n log n) - 空间复杂度：取决于排序实现。
三种解法对比
| 解法 | 时间复杂度 | 空间复杂度 | 特点 |
|---|---|---|---|
| 摩尔投票法 | O(n) | O(1) | 最优解法，不需要额外空间 |
| 哈希表统计 | O(n) | O(n) | 思路直观，需要额外空间 |
| 排序 | O(n log n) | 取决于实现 | 代码最短，效率较低 |
面试中优先写摩尔投票法，它展示了对算法的深入理解。