经典题解析：数组里出现次数过半的数，O(n) 时间 O(1) 空间怎么做到

图 1：本文封面，点明题目与摩尔投票法的复杂度承诺。

先说明属性：这是一篇经典题解析，题目出自本地历史面试资料（见文末来源说明），与任何公司的当前招聘无关。「找数组中出现次数超过一半的元素」这道题，几乎人人都能答出哈希计数，面试官真正想听的是那句进阶要求：O(n) 时间、O(1) 空间，怎么做？

想象面试现场，面试官写下题目：给定一个长度为 n 的数组，其中存在一个数出现次数超过一半，请找出它；进阶——不许开哈希表。

第一步，审题。

先把两个台阶摆出来。台阶一：哈希表统计每个数出现次数，返回过半的那个，时间 O(n)、空间 O(n)，正确但过不了进阶关。台阶二：排序后取中位数——如果过半元素存在，它一定占住中间位置，但排序要 O(n log n)。这两个答案都值得讲，它们是你的正确性基准，也是衬托更优解的背景板。真正的问题只有一个：能不能不开额外存储、也不排序？

第二步，核心直觉：一对一兑子。

换个角度看「过半」：这个数的数量比其它所有数加起来还多。于是可以玩一个抵消游戏——把两个不同的数配成一对扔掉，扔到最后，场上剩下的必然是过半的那个数。多数派和少数派一对一兑子，多数派一定有剩余。这就是摩尔投票法（Boyer-Moore Majority Vote）的全部直觉。

第三步，把直觉落成遍历规则。

维护两个变量：候选人 candidate 和净票数 count。遍历数组：count 为 0 时，把当前数立为新候选人；当前数与候选人相同，count 加一；不同，count 减一——这一步就是「兑子」。遍历结束时 candidate 就是过半元素。全程一遍扫描、两个变量，O(n) 时间、O(1) 空间，进阶要求达成。

有一个必须补的细节：以上结论依赖「过半元素存在」这个前提。如果题目不保证存在，兑子剩下的候选人可能是滥竽充数的——比如 [1,1,2,2] 会留下一个候选人但没有任何数过半。所以严谨的做法是第二阶段再扫一遍重新计数，确认候选人真的过半。

图 2：摩尔投票的计票轨迹与第二阶段验证。

第四步，写出可运行的代码。

下面这份实现包含摩尔投票、第二阶段验证、排序法复核，用 Node.js 22.15.0 直接运行（node majority-vote.js）即可：

'use strict';

// 摩尔投票法：candidate 为候选人，count 为净票数
function majorityVote(nums) {
  let candidate = null;
  let count = 0;
  for (const num of nums) {
    if (count === 0) {
      candidate = num; // 票数为 0：立当前数为新候选人
      count = 1;
    } else if (num === candidate) {
      count++; // 相同：票数加一
    } else {
      count--; // 不同：一对一抵消
    }
  }
  return candidate;
}

// 第二阶段：重新计数验证（题目不保证过半元素存在时必须做）
function findMajority(nums) {
  const candidate = majorityVote(nums);
  if (candidate === null) return null;
  const times = nums.filter((n) => n === candidate).length;
  return times > nums.length / 2 ? candidate : null;
}

// 对照组：排序取中位数（若过半元素存在，中位一定是它）
function findMajorityBySort(nums) {
  const sorted = [...nums].sort((a, b) => a - b);
  const mid = sorted[Math.floor(sorted.length / 2)];
  const times = nums.filter((n) => n === mid).length;
  return times > nums.length / 2 ? mid : null;
}

const cases = [
  [3, 2, 3, 4, 3, 3, 1],
  [2, 2, 1, 3, 2, 2, 4, 2],
  [1, 1, 2, 2],
  [5],
  [7, 7, 7, 1, 2, 7, 7, 8, 7],
];
for (const nums of cases) {
  const vote = findMajority(nums);
  const check = findMajorityBySort(nums);
  console.log(
    `[${nums}] -> 摩尔投票 ${vote === null ? '不存在' : vote}，` +
      `排序法复核 ${check === null ? '不存在' : check}`
  );
  if (vote !== check) throw new Error('两种方法结果不一致');
}

实测输出如下：

[3,2,3,4,3,3,1] -> 摩尔投票 3，排序法复核 3
[2,2,1,3,2,2,4,2] -> 摩尔投票 2，排序法复核 2
[1,1,2,2] -> 摩尔投票 不存在，排序法复核 不存在
[5] -> 摩尔投票 5，排序法复核 5
[7,7,7,1,2,7,7,8,7] -> 摩尔投票 7，排序法复核 7

五个用例两种方法结果全部一致，包括「不存在过半元素」和单元素数组两个边界。

易错点清单。

一，忘记验证阶段——前提不保证时，投票结果必须重新计数确认。二，把「count 减到 0 才换人」写成「遇到不同就换人」，兑子节奏错了结果就全错。三，把「过半」理解成「至少一半」——> 和 >= 在偶数长度数组上结论不同，验证代码里必须严格大于。四，背得出 O(1) 空间却讲不出兑子直觉——面试官追问「为什么剩下的就是它」，答「因为票多」等于没答。

回到面试现场，建议的答题节奏：先给哈希计数作为正确基准并指出空间 O(n)，再讲一对一兑子的直觉，然后写出三个分支的遍历规则，最后主动补上「不保证存在时需要第二遍验证」这个严谨性加分点。

摩尔投票是流式多数统计的经典算法，模型集成的投票机制、在线标注聚合里都能找到它的影子。你还知道哪些「用抵消代替计数」的算法？欢迎举例。

参考资料

• Node.js v22.x 官方 API 文档（文中代码运行环境为 Node.js 22.15.0，Array.prototype.filter、sort 等行为以此为准） — https://nodejs.org/docs/latest-v22.x/api/