169. 多数元素

难度：🟢 Easy | 标签：摩尔投票 | 状态：⬜ LeetCode 链接

思路

摩尔投票：候选 + 计数。

• 计数为 0 → 换候选
• 当前元素等于候选 → +1
• 不等 → -1

因为多数元素出现次数 > n/2，最终候选一定是答案。

代码

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int cand = 0, cnt = 0;
        for (int x : nums) {
            if (cnt == 0) cand = x;
            cnt += (x == cand) ? 1 : -1;
        }
        return cand;
    }
};

复杂度

• 时间 O(n)，空间 O(1)

易错 / 回顾

• 题目保证多数元素存在，所以不用第二次验证
• 不存在保证时要再扫一次验证
• 229（多数 ≥ n/3）：扩展到双候选