手帐 Blog

主题

复盘 · LC 169 多数元素 ​

题目 ​

题意 ​

数组 nums 中，多数元素指出现次数 大于 ⌊n / 2⌋ 的元素。题目保证多数元素一定存在，返回它即可。

  • 不必处理「没有多数」的情况。
  • 边界：[1]、[2,2,1,1,1,2,2]、全相同、多数刚好刚过半。

涉及算法 ​

标签一句话
哈希计数扫一遍记频率，取 max / 或 count > n/2 提前返回
Boyer-Moore 投票候选人互相抵消；多数派最后一定留下
排序排序后下标 ⌊n/2⌋ 一定是多数元素

教程对照：09 · 哈希表进阶（计数套路）；数组扫描手感见 04。

评价我的解法 ​

你的思路：Map 全量计数，再扫一遍找出现次数最大的 key。在「保证存在多数」的前提下正确——多数元素频率一定是最大的。

我的代码（摘自 169-多数元素/index.js，不含本地测例）：

javascript
var majorityElement = function (nums) {
  const resMap = new Map();
  nums.forEach((val, index) => {
    const count = resMap.get(val) || 0;
    resMap.set(val, count + 1);
  });
  // console.log(resMap);
  let max = 0;
  let maxKey = 0;
  resMap.forEach((val, key) => {
    if (val >= max) {
      max = val;
      maxKey = key;
    }
  });
  return maxKey;
};

务实评价：

  1. 正确性：能 AC；val >= max 在并列时取后出现的 key，本题不会并列到两个都 > n/2，所以安全。
  2. 没用上「> n/2」：计数时若 count > nums.length / 2 可直接 return，少一次全表扫描。
  3. 复杂度：时间 O(n)，空间 O(n)；面试常追问 O(1) 空间 → 投票或排序（排序要 O(1)/O(log n) 额外空间看实现）。
  4. 小糙点：index 未用；注释掉的 console.log 可删；maxKey 初值 0 在空数组会误导（题目非空，无妨）。

小结：哈希计数是标准保底解；下一步把 Boyer-Moore 默写进肌肉记忆。

最佳题解 ​

Boyer-Moore 投票（O(1) 空间）：

javascript
/**
 * @param {number[]} nums
 * @return {number}
 */
var majorityElement = function (nums) {
  let candidate = nums[0];
  let count = 0;
  for (let i = 0; i < nums.length; i++) {
    if (count === 0) candidate = nums[i];
    count += nums[i] === candidate ? 1 : -1;
  }
  return candidate;
};
  • 时间 O(n)，空间 O(1)。
  • 为何更优：多数元素出现超过一半，抵消后候选人必是它；题目保证存在，无需第二遍校验。

哈希优化版：计数中一旦 > ⌊n/2⌋ 立即返回，仍 O(n) 空间，但常数与写法更贴题意。

关联题目 ​

题为何相关
229. 多数元素 II出现 > ⌊n/3⌋；扩展投票（两个候选人）
136. 只出现一次的数字同日题；都是「找特殊出现次数」
215. 数组中的第K个最大元素排序/选择；多数元素的「取中位」思路同类

一句话带走 ​

多数元素：哈希计数保底；面试加分讲 Boyer-Moore 投票，O(1) 空间。