LeetCode 229. 多数元素 II

2025-12-22 HGNULB 约 9 分钟

文章信息 8 个分类 5 个标签

分类

题目描述

✅ 229. 多数元素 II

题意分析

要找出数组里所有出现次数严格超过 $\lfloor n/3 \rfloor$ 的元素，结果顺序不限。注意是「严格超过」而不是「不少于」，这一个字直接决定了最后那步判断用 > 还是 >=。

数组长度最大 5 × 10^4，元素取值覆盖整个 int 范围（含负数和 Integer.MIN_VALUE），所以不能开值域数组，也不能想当然地把 0 当作「不可能出现的哨兵值」。

题目最下方的进阶要求是「时间 $O(n)$、空间 $O(1)$」。这一条才是本题真正的考点：用哈希表计数谁都会写，但空间是 $O(n)$，达不到要求。

一个必须先自己算清楚的数量关系：满足条件的元素最多只有两个。假如有三个不同元素各自出现超过 $n/3$ 次，它们的次数之和就会严格大于 n，超出数组总长度，矛盾。所以答案的长度只可能是 0、1 或 2。

边界上要覆盖：数组长度为 1（此时 $\lfloor 1/3 \rfloor = 0$，唯一那个元素出现 1 次，必须被选出）、所有元素相同、以及不存在任何满足条件元素这三种情况。

解法：扩展 Boyer-Moore 投票

核心思路

最直接的做法是哈希表统计每个值的出现次数，再挑出次数大于 $\lfloor n/3 \rfloor$ 的。时间 $O(n)$ 没问题，但哈希表最坏会存下 n 个不同的键，空间是 $O(n)$，卡在进阶要求上。

瓶颈在于「记住了太多无关信息」。既然答案至多两个，那么绝大多数键的计数从头到尾都用不上，真正需要留在内存里的只有两个候选值。

顺着这个方向的关键观察是「三三抵消」：从数组里任取三个互不相同的元素同时删掉，任何一个原本出现次数超过 $n/3$ 的元素，在删除后的数组里仍然超过新长度的三分之一。理由是每删一组，该元素最多损失 1 次，而总长度减少了 3，比例只会更有利。把这个操作反复做到底，剩下的元素至多只有两种取值，答案必然在其中。

于是维护两个「席位」：候选值 cand1、cand2 与各自的票数 count1、count2。整趟扫描保持的不变量是——把已扫描前缀中被成对成组抵消掉的元素全部拿走后，剩下的元素只由 cand1 和 cand2 组成，且各自恰好剩 count1、count2 个；票数为 0 表示该席位当前是空的，上面残留的值没有任何意义。

这个不变量只保证「答案一定在两个席位里」，反过来不成立：席位上的值可能根本没达到次数要求。所以投票只是把候选从 n 个压到 2 个，最后还必须回头再数一遍它们的真实次数。

解题步骤

初始化 cand1、cand2 为任意值，count1、count2 置 0。之所以不能靠「特殊初值」来表示空席位，是因为元素可以取任何 int 值；判空只能看票数是否为 0。

遍历数组，对每个 num 依次尝试四类分支，顺序不能乱：先判「count1 > 0 且 num == cand1」，再判「count2 > 0 且 num == cand2」，然后判「count1 == 0」，再判「count2 == 0」，最后才是双双减票。

前两个分支必须带上票数非零的前提，否则会把空席位上的残留值当成有效候选，凭空给它加票。

命中已有候选就加票，对应「这一票投给它」；席位空就占座并置票数为 1，对应「新开一个候选」；两个席位都被别的值占着，就把 count1 和 count2 同时减一，对应「num、cand1、cand2 三个互不相同的元素成组抵消」。

第二趟重新扫描数组，只统计票数仍大于 0 的席位对应值的真实出现次数。这一趟不能省，也不能直接拿 count1、count2 当次数用，因为票数是抵消后的残值，远小于真实出现次数。

最后用真实次数与 nums.length / 3 比较，严格大于才加入结果。整数除法本身就是向下取整，不需要额外处理。

以 nums = [1,1,1,3,3,2,2,2] 走一遍：初始两个席位都空。读到第一个 1，count1 为 0，于是 cand1 = 1、count1 = 1。第二个 1 命中 cand1，count1 = 2。第三个 1 再命中，count1 = 3。读到 3，不等于 cand1 且 count2 为 0，于是 cand2 = 3、count2 = 1。第二个 3 命中 cand2，count2 = 2。读到第一个 2，既不等于 1 也不等于 3，两个席位都非空，于是同时减票，count1 = 2、count2 = 1。第二个 2 再次触发抵消，count1 = 1、count2 = 0。第三个 2 到来时 count2 已为 0，席位空出，于是 cand2 = 2、count2 = 1。投票结束，两个候选是 1 和 2。第二趟数真实次数：1 出现 3 次，2 出现 3 次。阈值是 8 / 3 = 2，两者都严格大于 2，返回 [1, 2]。注意残留票数 count1 = count2 = 1 与真实次数 3 完全对不上，这直接说明了第二趟验证为什么不可省略。

代码实现

class Solution {
    // 投票阶段维护两个候选值和对应票数，遇到第三种不同数字时同时抵消三者各一次。
    public List<Integer> majorityElement(int[] nums) {
        int cand1 = 0;
        int cand2 = 0;
        int count1 = 0;
        int count2 = 0;
        for (int num : nums) {
            if (count1 > 0 && num == cand1) {
                count1++;
            } else if (count2 > 0 && num == cand2) {
                count2++;
            } else if (count1 == 0) {
                cand1 = num;
                count1 = 1;
            } else if (count2 == 0) {
                cand2 = num;
                count2 = 1;
            } else {
                count1--;
                count2--;
            }
        }

        int actual1 = 0;
        int actual2 = 0;
        for (int num : nums) {
            if (count1 > 0 && num == cand1) {
                actual1++;
            } else if (count2 > 0 && num == cand2) {
                actual2++;
            }
        }

        List<Integer> res = new ArrayList<>();
        if (actual1 > nums.length / 3) {
            res.add(cand1);
        }
        if (actual2 > nums.length / 3) {
            res.add(cand2);
        }

        return res;
    }
}

func majorityElement(nums []int) []int {
    // 投票阶段维护两个候选值和对应票数，遇到第三种不同数字时同时抵消三者各一次。
    cand1, cand2 := 0, 0
    count1, count2 := 0, 0
    for _, num := range nums {
        if count1 > 0 && num == cand1 {
            count1++
        } else if count2 > 0 && num == cand2 {
            count2++
        } else if count1 == 0 {
            cand1 = num
            count1 = 1
        } else if count2 == 0 {
            cand2 = num
            count2 = 1
        } else {
            count1--
            count2--
        }
    }

    actual1, actual2 := 0, 0
    for _, num := range nums {
        if count1 > 0 && num == cand1 {
            actual1++
        } else if count2 > 0 && num == cand2 {
            actual2++
        }
    }

    res := make([]int, 0)
    if actual1 > len(nums)/3 {
        res = append(res, cand1)
    }
    if actual2 > len(nums)/3 {
        res = append(res, cand2)
    }

    return res
}

复杂度分析

时间复杂度：$O(n)$，投票一趟、验证一趟，共两次线性扫描，每个位置只做常数次比较和加减。

空间复杂度：$O(1)$，不计返回值时只用到两个候选值和两个计数器，与输入规模无关。

关键点总结

先把「答案最多几个」用反证法算清楚，再决定维护几个席位；求超过 $n/k$ 的元素就需要 k - 1 个席位，这个结论可以直接推广。

投票法的本质是「成组抵消不改变超额元素的超额性」，把它讲成不变量比背分支写法更稳，临场也不容易漏掉票数非零的前提。

「筛选 + 验证」两段式是这类算法的固定形态：第一段负责把候选压到常数个，第二段负责保证正确性，缺了第二段答案就只是猜测。

不能用特殊值表示「空」的场景很常见，判空要另设标志位（这里是票数），而不是依赖某个魔法初值。

面试视角：这题的采分点不在能不能写对，而在能不能主动说出进阶要求 $O(1)$ 空间、能不能证明答案至多两个、以及能不能解释清楚为什么必须二次验证。被追问「推广到超过 $n/k$」时要能立刻答出维护 k - 1 个候选、时间 $O(nk)$、空间 $O(k)$。

易错点总结

错误写法：省掉第二趟验证，直接把票数大于 0 的候选返回 → nums = [1,2,3] 时投票结束后两个席位上会残留候选，但没有任何元素出现超过 1 次，正确答案是空数组。

错误写法：把 count1、count2 当成真实出现次数去和 n / 3 比较 → nums = [1,1,1,3,3,2,2,2] 中 1 的残留票数只有 1，会被误判为不达标，漏掉正确答案。

错误写法：Java 里把候选存成 Integer 并用 == 比较 → 数值超出 -128 到 127 的缓存区间后比较的是对象引用，nums 全为 1000 时同一个值也会被判为不等，投票整个失效。

错误写法：用 Integer.MIN_VALUE 之类的哨兵表示空席位 → 数组里本来就允许出现该值，真实数据会被误认成空位，nums 全为 Integer.MIN_VALUE 时直接返回空数组。

错误写法：把「占用空席位」的分支排在「命中已有候选」之前 → 一个已经坐在 2 号席位上的值可能被复制到 1 号席位，两个席位退化成同一个值，等于只剩一个有效候选，遇到确实有两个答案的输入就会漏解。

错误写法：抵消时只把其中一个席位的票数减一 → 不变量被破坏，另一个席位会虚高地占着位置，真正满足条件的元素挤不进候选，最终漏解。

错误写法：最后判断写成 >= → nums = [1,1,2] 时阈值为 1，2 只出现 1 次也会被算进去，返回 [1,2]，而正确答案是 [1]。

错误写法：先算 n / 3 再对结果做四舍五入或加一 → 题意就是向下取整后严格大于，整数除法已经是想要的语义，任何额外修正都会在 n 不是 3 的倍数时出错。

相似题目

题目	难度	考察点
169. 多数元素	简单	只需一个席位，且题目保证答案存在，可省掉验证
剑指 Offer 39. 数组中出现次数超过一半的数字	简单	与 169 同题，可顺带练排序取中位数的写法
面试题 17.10. 主要元素	简单	单席位但不保证存在，必须补验证并返回 -1