169. 多数元素（Majority Element）

频次 ★★★★ · 难度 🟢 · 高频：字节/腾讯/美团

题目

给定一个大小为 n 的数组，找出其中的多数元素。多数元素指在数组中出现次数大于 ⌊n/2⌋ 的元素。可以假设数组非空且多数元素一定存在。

示例：

输入: [2,2,1,1,1,2,2]
输出: 2

思路

摩尔投票（Boyer-Moore Voting）：维护一个候选元素 candidate 和计数器 count：

• 当 count == 0 时，将当前元素设为候选，count = 1
• 否则如果当前元素等于候选，count++
• 否则 count--

核心思想：不同元素相互抵消，多数元素由于数量占优，最终一定会留在候选位上。

也可以排序取中间元素（O(n log n)）或哈希表统计（O(n) 空间），但不是本题考察的最优解。

代码

public int majorityElement(int[] nums) {
    int candidate = 0, count = 0;
    for (int num : nums) {
        if (count == 0) {
            candidate = num;
            count = 1;
        } else if (num == candidate) {
            count++;
        } else {
            count--;
        }
    }
    return candidate;
}

复杂度

• 时间：O(n) —— 一次遍历
• 空间：O(1)

边界条件

• 长度 1：唯一元素就是答案，count 从 0→1，candidate 为该元素
• 全部相同：count 一路增加到 n，candidate 不变
• 多数元素刚好超过一半：摩尔投票仍正确，因为其他元素全部加起来也抵消不掉多数元素

变式

• 229. 求众数 II：找出现次数 > ⌊n/3⌋ 的元素，需要两个候选，两次遍历校验
• 验证是否存在多数元素：第一步投票得候选，第二步遍历计数确认，本题保证存在所以省略了验证步骤
• 分治法：数组分成两半，递归找各自众数，合并时比较两个候选谁在整个区间出现更多

易错点

• 摩尔投票只能保证候选是潜在多数元素，如果题目不保证存在多数元素，需要用第二遍遍历验证
• count == 0 的判断必须在 else if 之前，否则切换候选的时机不对
• 不要把摩尔投票和快慢指针或其他双指针模式混淆——摩尔投票本质是”配对抵消”不是”快慢追赶”

面试追问

• 摩尔投票的原理是什么？ 多数元素的数量比其他所有元素加起来还要多，每次消去一对不同的元素，多数元素的绝对数量优势不会消失。最终留下来的就是多数元素
• 如果题目不保证存在多数元素呢？ 第一轮投票后需要再遍历一遍数组，统计候选的出现次数是否真的 > n/2。这个”投票 + 验证”两步走是完整版摩尔投票
• 还有其他解法吗？ 排序（O(n log n)），哈希表计数（O(n) 空间），随机化采样（期望 O(n)），分治（O(n log n)）。面试中摩尔投票是最优解，排序是最保险的备选

关联题

• 同套路：229. 求众数 II —— 超过 n/3 的众数，两个候选加验证
• 进阶：1157. 子数组中占绝大多数的元素 —— 线段树维护区间众数，摩尔投票可合并
• 知识点：摩尔投票——配对抵消思想，见数组与字符串