一道数组面试题，搞懂摩尔投票法

Posted on

在前端/全栈算法面试中，「多数元素」是一道非常经典的简单题。最容易想到的解法是用哈希表统计每个数字出现次数，遍历后找到大于 n/2 的元素。哈希表思路直观，但需要 O(n) 的额外空间。

面试官经常会追加一个进阶问题：能不能在 O(n) 时间复杂度，O(1) 空间复杂度完成？

这时候，摩尔投票法（Boyer-Moore Majority Vote Algorithm）就是最优解。

题目描述

给定一个大小为 n 的数组 nums，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
题目保证数组非空，且一定存在多数元素。

示例：
输入：[2,2,1,1,1,2,2]
输出：2

解释：数组长度为7，多数元素出现次数需要大于3.5，也就是至少4次。数字2一共出现4次，满足条件。

摩尔投票法核心思想：相互抵消

摩尔投票的核心逻辑可以用一句话概括：不同元素相互抵消，相同元素累加。

我们可以把数组里每一个数字想象成不同阵营的士兵：

  1. 遇到和当前候选相同的士兵，己方兵力+1；
  2. 遇到敌方士兵，双方同归于尽，己方兵力-1；
  3. 如果己方兵力归零，代表当前阵营全部阵亡，更换新的候选士兵。

本题有一个关键前提：多数元素出现次数 > 数组长度的一半。
也就是说，多数元素的总数量，大于剩下所有其他元素数量之和。
无论怎么两两抵消，最后剩下存活的候选，一定是这个多数元素。

⚠️ 重要提醒：如果题目不保证一定存在大于 n/2 的众数，摩尔投票得到的候选不能直接作为答案，必须再遍历一次数组，校验该候选的实际出现次数。

算法执行流程演示

以数组 [2,2,1,1,1,2,2] 举例：

  • 初始候选：2，计数 count = 1
  • i=1，元素2：相同，count=2
  • i=2，元素1：不同，count=1
  • i=3，元素1：不同，count=0，兵力耗尽
  • i=4，元素1：count=0，更换候选为1，count=1
  • i=5，元素2：不同，count=0，兵力耗尽
  • i=6，元素2：count=0，更换候选为2，count=1

遍历结束，候选值为2，就是数组的多数元素。

复杂度分析

  • 时间复杂度：O(n)，仅遍历数组一次
  • 空间复杂度：O(1)，只使用两个变量，不需要额外开辟存储空间

对比哈希表解法：哈希表同样O(n)时间，但需要O(n)空间存储每个数字的计数。大数据场景下摩尔投票优势明显。

TypeScript 代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/**
 * 摩尔投票法求解多数元素
 * @param nums 数字数组，题目保证存在出现次数大于 n/2 的元素
 * @returns 多数元素
 */
function majorityElement(nums: number[]): number {
    // 当前候选元素
    let candidate = nums[0];
    // 候选计数
    let count = 1;

    // 从第二个元素开始遍历
    for (let i = 1; i < nums.length; i++) {
        if (count === 0) {
            // 兵力归零，更换候选
            candidate = nums[i];
            count = 1;
        } else if (nums[i] === candidate) {
            // 相同元素，计数累加
            count++;
        } else {
            // 不同元素，相互抵消
            count--;
        }
    }
    return candidate;
}

// 测试用例
console.log(majorityElement([2,2,1,1,1,2,2])); // 2
console.log(majorityElement([3,2,3])); // 3

拓展版本（无“一定存在多数元素”的前提，增加校验）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
function majorityElementCheck(nums: number[]): number | null {
    let candidate = nums[0];
    let count = 1;
    for (let i = 1; i < nums.length; i++) {
        if (count === 0) {
            candidate = nums[i];
            count = 1;
        } else if (nums[i] === candidate) {
            count++;
        } else {
            count--;
        }
    }
    // 二次遍历校验候选是否满足条件
    let total = 0;
    for (const num of nums) {
        if (num === candidate) total++;
    }
    return total > nums.length / 2 ? candidate : null;
}

面试小结

  1. 摩尔投票适合：寻找出现次数大于数组一半的元素；
  2. 核心是抵消思想，O(1)空间是面试加分项；
  3. 一定要记住边界：题目如果不保证存在众数，必须额外校验。