LeetCode 面试题 17.10. 主要元素

2026-03-28 HGNULB 约 6 分钟

文章信息 3 个分类 2 个标签

分类

题目描述

✅ 面试题 17.10. 主要元素

题意分析

给定长度为 n 的数组，返回其中出现次数严格超过 ⌊n / 2⌋ 的那个元素。

「超过一半」是一个非常强的条件：这个元素比其余所有元素加起来还多。这意味着答案是唯一的——不可能有两个元素同时超过一半。

题目还明确承诺「数组总是存在多数元素」。这个前提很关键：它意味着我们只需要「找出可能的答案」，而不需要「验证它确实是答案」。如果没有这条保证，任何只扫一遍就下结论的做法都必须补一次验证。

边界方面：n 可以为 1（单元素自己就是多数元素）；元素可以是负数，所以不能拿元素值本身当计数器的哨兵。

解法：Boyer-Moore 投票法

核心思路

暴力：用哈希表统计每个元素出现次数，超过 n / 2 的就是答案，时间 $O(n)$ 但空间 $O(n)$；排序后取 nums[n / 2] 也一定是多数元素，可作对照解法，但时间 $O(n \log n)$。面试官通常会追问：能不能 $O(n)$ 时间加 $O(1)$ 空间？

观察：多数元素超过一半，于是有一个关键性质——从数组中删掉两个不同的元素，多数元素在剩余数组中仍然是多数元素。原因：设多数元素出现 c 次，c > n / 2。删掉的两个元素中至多有一个是多数元素，删除后它至少还有 c - 1 次，而剩余长度是 n - 2；由 c > n / 2 可得 c - 1 > (n - 2) / 2，多数地位不变。

Boyer-Moore 投票法就是把「成对删除不同元素」做成一次遍历：维护候选 candidate 和票数 count。遇到与候选相同的元素票数加一；遇到不同的元素票数减一——相当于把「一个候选 + 一个异己」这对不同元素抵消删除。票数归零表示前面这一段已经完全两两抵消，从下一个元素重新开始选候选。

显式不变量：任意时刻，把数组看成「已完全抵消的前缀 + 当前候选剩余的 count 张票 + 未处理的后缀」。每次抵消删除的都是两个不同元素，由上面的性质，多数元素在「未被抵消的部分」中始终保持多数。遍历结束后未被抵消的只剩候选的 count 张票（count ≥ 1，因为多数元素不可能被全部抵消掉），所以候选必然就是多数元素——这就是「为什么最后剩下的一定是多数」的完整回答。

解题步骤

初始化 candidate = 0、count = 0。初始值取什么都行，因为第一个元素到来时 count == 0，必然先被立为候选——这也是负数元素不构成问题的原因。

遍历每个元素 num：若 count == 0，令 candidate = num。为什么：票数归零说明之前的元素已两两抵消完毕，历史不再影响后续，相当于在剩余数组上重新开局。

接着比较：num == candidate 则 count++，否则 count--。为什么减而不是换：减一对应「删掉一个候选和一个异己」这对不同元素，抵消不改变多数元素的多数地位。

遍历结束直接返回 candidate。为什么不用验证：题目保证多数元素存在，而不变量保证存在时候选必为它。

以 [2,2,1,1,1,2,2] 走一遍：读 2，count == 0，候选 = 2，count = 1；读 2，相同，count = 2；读 1，不同，count = 1；读 1，不同，count = 0（前四个元素两两抵消）；读 1，count == 0，候选 = 1，count = 1；读 2，不同，count = 0；读 2，count == 0，候选 = 2，count = 1。遍历结束返回 2，正确。

代码实现

class Solution {
    public int majorityElement(int[] nums) {
        int candidate = 0;
        int count = 0;

        for (int num : nums) {
            if (count == 0) {
                candidate = num;
            }
            // 不同元素互相抵消，多数元素最终会留下。
            if (num == candidate) {
                count++;
            } else {
                count--;
            }
        }

        return candidate;
    }
}

func majorityElement(nums []int) int {
    candidate := 0
    count := 0

    for _, num := range nums {
        if count == 0 {
            candidate = num
        }
        // 候选值和其他值两两抵消。
        if num == candidate {
            count++
        } else {
            count--
        }
    }

    return candidate
}

复杂度分析

时间复杂度：$O(n)$，单次遍历数组，每个元素只做常数次比较和加减。

空间复杂度：$O(1)$，只维护 candidate 和 count 两个变量，与输入规模无关。

关键点总结

「超过一半」这类强约束往往就是优化的入口：它换来的性质是「删掉两个不同元素，多数仍是多数」，整套投票法建立在这一条抵消论证之上。

count 不是候选的真实出现次数，而是「候选未被抵消的净票数」，两者在语义上必须分清，面试口述时混用会被追问。

count == 0 时切换候选的本质是「前缀已完全抵消，可以在剩余数组上重新开局」，这是子问题结构，不是随意的重置。

面试视角：答完投票法后，最常见的追问是「为什么最后剩下的一定是多数」和「如果不保证多数存在怎么办」——前者用抵消不变量回答，后者补一次 $O(n)$ 计数验证。

投票法可以推广：找出现次数超过 n / 3 的元素时维护两个候选（229 题），核心仍是「删 k + 1 个互不相同的元素不改变超过 n / (k + 1) 的多数地位」。

易错点总结

错误写法：没有多数保证时直接返回投票结果。反例 [1,2,3] 中，投票法最终候选是 3，但它并非多数元素；题面不保证时必须再扫一遍统计候选的真实次数做验证。

count == 0 判断放在增减票之后：[1,2,2] → 第二个元素 2 先把 count 减到 -1 再谈换人，候选切换时机全部错位，返回错误候选。

票数减到 0 时立刻把当前元素立为候选：[2,1,2] → 读 1 时 count 归零就顺手把 1 立为候选，等于让异己白得一票，正确写法是等下一个元素到来、count == 0 时再立。

把 count 当成真实出现次数返回或使用：[2,1,2,1,2] → 结束时 count = 1，但 2 实际出现 3 次；用 count 做任何「次数」判断都会出错。

用 candidate 初始值当哨兵判断「还没有候选」：元素含 0 或负数的数组如 [0,0,-1] → 以 candidate == 0 表示「无候选」会误判，必须只靠 count == 0 判断。

遍历中途 count 归零就提前下结论：[1,1,2,2,2] → 前四个元素抵消后 count = 0，若此时认为「没有多数」或返回旧候选就漏掉了后缀，必须完整遍历。

写成「不同就换候选」而不是「不同就减票」：[2,3,2,3,2] → 每遇到不同元素就直接换人，候选跟着最后一个元素走，多数元素的票数优势完全没有累积。

相似题目

题目	难度	考察点
229. 多数元素 II	中等	投票法推广到超过 `n / 3`，双候选且必须二次验证
剑指 Offer 39. 数组中出现次数超过一半的数字	简单	同题异面，练习口述抵消不变量