LeetCode 229. 多数元素 II

约 6 分钟
文章信息 8 个分类 4 个标签
分类
LeetCode CodeTop 中等 未解决 2-5 字节 阿里 滴滴
标签
数组 哈希表 排序 计数

题目描述

✅ 229. 多数元素 II

image-20260928224221470

题意分析

返回数组中出现次数严格大于 floor(n / 3) 的所有不同数值，答案可能为空，也可能有一个或两个值。若有三个值都超过三分之一，总次数就会超过数组长度，所以不可能有更多答案。

与保证多数元素存在的题目不同，本题不保证候选一定合格。进阶要求线性时间、常数辅助空间，因此需要少量候选筛选，再验证实际频次。

解法：扩展 Boyer-Moore 投票

核心思路

[!blue]

一次删掉三个互不相同的值，不会把真正超过三分之一的元素彻底删光。设它原有 c 次且 3c > n，若这一组含它，删后仍有 3(c - 1) > n - 3；若不含它，它的占比只会更高。因此可以不断抵消三种不同值，只保留剩余候选。

用 cand1、cand2 表示至多两种未抵消的值，count1、count2 表示各自剩余票数。新值命中某个有效候选就加票；没有命中但有空位，就让它占据空位并获得第一票；两位均有效且都不匹配时，当前值与两个候选各抵消一次，将两个计数同时减一。

判断顺序必须先匹配已有的有效候选，再填空位。否则新值即使与另一个候选相同，也可能占据空席，让同一个值同时出现在两个位置，破坏三种不同值抵消的前提。

每一步都把已读部分表示为若干已删除的异值三元组，加上最多两种剩余值。真正的多数一定保留在最终的有效候选中，所以不会漏掉；但较少出现的值也可能因扫描末尾的顺序留下，单靠投票不能确认答案。

因此第二次扫描原数组，重新统计有效候选的实际次数，只输出严格超过 n / 3 的候选。投票余量与真实频次用途不同，不能直接拿剩余票数判断阈值。

解题步骤

  1. 初始化两个候选席位及零票数，零票表示当前席位无效。
  2. 遍历数字，依次尝试命中已有候选、占用空席，最后才执行三值抵消。
  3. 保留最终有效候选，另设实际计数器，再完整扫描一次原数组。
  4. 将实际次数严格大于 nums.length / 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)$，最多两名候选及计数。

关键点总结

[!green]

  • 数量上限决定只需两个候选，三种异值抵消保证真正多数不会消失。
  • 先命中已有候选，再接纳新值，确保两个有效候选始终不同。
  • 投票只缩小候选范围，第二次实际计数才判断资格。
  • 零票席位的旧值没有效力，验证时也只统计仍有效的候选。

易错点总结

[!yellow]

  • 直接返回最终候选，会把未达阈值的残留值误当成答案。
  • 使用抵消后的票数验证，可能把真正多数误删，应重新统计原数组。
  • 先填空位再匹配已有候选，可能让同一值占据两席。
  • 阈值是严格大于，不能把恰好出现三分之一的值加入结果。

相似题目

题目 难度 关联与区别
169. 多数元素 简单 阈值从超过一半降到超过三分之一，最多候选数从1变成2。
面试题 17.10. 主要元素 简单 同样不能仅凭抵消后的候选直接返回，最终需要重新统计真实次数验证阈值。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2025/58482309
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！