.jpg)
748 字
4 分钟
多数元素
题目描述
给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
解题思路
- 核心算法选择：采用 Boyer-Moore 投票算法，通过模拟元素间的”抵消”过程高效找出候选多数元素。
- 初始化设置：定义
candidate存储候选元素，count计数器（初始为 0）。 - 遍历与抵消机制：
- 若
count=0，将当前元素设为candidate，count=1； - 若当前元素等于
candidate，count++； - 否则
count--（模拟抵消）。
- 若
- 结果验证：二次遍历统计
candidate出现次数，确认是否严格大于 n/2。
关键洞察
- 数量优势特性：多数元素出现频率 > n/2，其数量超过其他元素总和，抵消后必然剩余。
- 动态重置机制：当
count=0时，表示前序子数组无多数元素，可安全切换候选而不影响全局结果。 - 无损压缩信息：算法通过计数器动态维护候选状态，避免存储全量数据，空间复杂度降至常数级。
- 边界兼容性：若数组无多数元素，验证步骤（第二次遍历）能确保结果正确性。
复杂度分析
| 指标 | 说明 |
|---|---|
| 时间复杂度 | O(n)：遍历数组两次（首次投票 + 二次验证），每次遍历处理 n 个元素的操作均为常数时间。 |
| 空间复杂度 | O(1)：仅使用 candidate（存储元素）、count（整数计数器）等固定数量的额外变量，与输入规模无关。 |
代码实现
投票算法实现
/** * 寻找数组中的多数元素（出现次数 > n/2） * @param {number[]} nums 输入数组 * @return {number} 多数元素 */const majorityElement = (nums) => { // 投票算法第一阶段：寻找候选元素 let count = 0; let candidate = null;
for (const num of nums) { // 当计数器归零时，切换候选元素 if (count === 0) candidate = num; // 更新计数器：相同元素+1，不同元素-1 count += (num === candidate) ? 1 : -1; }
// 投票算法第二阶段：验证候选元素 // （根据题目假设可以省略，但保留以符合完整逻辑） const n = nums.length; const freq = nums.reduce((acc, cur) => acc + (cur === candidate ? 1 : 0), 0);
return freq > n / 2 ? candidate : null;};自己实现的
/** * @param {number[]} nums * @return {number} */var majorityElement = function (nums) { let winner = nums[0]; let count = 1; for (let i = 1, len = nums.length; i < len; i++) { if (winner === nums[i]) { count++; } else if (count === 0) { winner = nums[i]; count++; } else { count--; } } return winner;};