LeetCode 169. 多数元素

◎

本节目标

用 Boyer–Moore 投票抵消不同元素，在常数空间内保留多数候选。

查看 LeetCode 原题

题意与边界

数组非空，并保证存在出现次数严格超过一半的元素。利用这一保证直接返回多数候选，不需要第二遍验证合法性。

成对抵消

维护候选 candidate 和净票数 count。遇到候选就加一，遇到其他值就减一；当净票数归零时，之前扫描部分可以两两抵消，下一元素成为新候选。

正确性依据

从数组中任意删除一对不同元素，都不会改变“原多数元素仍是剩余序列多数元素”的事实。投票过程正是在流式完成这种抵消。由于多数元素数量超过其余元素总和，全部抵消结束后最终候选只能是多数元素。

代码实现

C++

C++17

#include <vector>
using namespace std;

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int candidate = 0;
        int count = 0;
        for (int num : nums) {
            if (count == 0) {
                candidate = num;
            }
            count += num == candidate ? 1 : -1;
        }
        return candidate;
    }
};

Python

Python 3

class Solution:
    def majorityElement(self, nums: list[int]) -> int:
        candidate = 0
        count = 0
        for num in nums:
            if count == 0:
                candidate = num
            count += 1 if num == candidate else -1
        return candidate

复杂度分析

• 时间复杂度：O(n)。
• 空间复杂度：O(1)。

易错点

• 当 count == 0 时，先把当前元素设为新候选，再为当前元素计一票。
• 忘记题目保证多数元素存在，却加入无必要的哈希计数或第二遍验证。
• 把多数条件误写成“至少一半”；题目保证的是出现次数严格大于 ⌊n/2⌋。

模式迁移

投票算法依赖强多数保证。若只保证高频但不超过一半，需要扩展候选数量或在最后重新计数，不能直接复用单候选结论。