LeetCode 面试题 17.10. 主要元素

约 4 分钟
文章信息 3 个分类 2 个标签
分类
LeetCode 简单 程序员面试金典（第 6 版）
标签
数组 计数

题目描述

✅ 面试题 17.10. 主要元素

image-20260929010514141

题意分析

找出出现次数严格超过数组长度一半的主要元素，不存在则返回 -1。这样的值至多有一个，但题目不保证它存在，所以选出候选后还必须检查实际次数。

解法：Boyer–Moore 投票后验证候选

核心思路

[!blue]

将不同数值的两个元素成对抵消。若主要元素存在，删掉这样一对时，它至多减少一个，而其他元素至少减少一个，所以它相对于其他所有值的数量优势不会减少。不断抵消后，它不可能被全部消掉。

扫描时用 candidate 和 count 模拟这个过程：count 表示已经抵消后，还剩多少个值为 candidate 的元素。遇到相同值就加 1，遇到不同值就用当前元素抵消一个候选，减 1。当 count = 0 时，前面的剩余元素已经全部抵消，可以把当前值作为新候选，从 1 开始重新累计。

扫描结束后，若主要元素存在，它一定是唯一可能留下的候选。但没有主要元素时也可能留下某个值，甚至计数恰好为零，所以第一趟不能直接给出结论。第二趟统计 candidate 在原数组中的真实出现次数，只有严格大于 n/2 才返回它，否则返回 -1。

解题步骤

  1. 初始化 count = 0，初始候选值不影响结果。
  2. 逐个读取元素；若余额为零，先把当前值设为候选，再按相同加 1、不同减 1 更新余额。
  3. 重新扫描数组，只统计最终候选的实际出现次数 occurrences。
  4. 检查 occurrences > n / 2，满足则返回候选，不满足则返回 -1。

代码实现

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--;
            }
        }

        int occurrences = 0;

        for (int num : nums) {
            if (num == candidate) {
                occurrences++;
            }
        }

        return occurrences > nums.length / 2 ? candidate : -1;
    }
}

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

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

    occurrences := 0
    for _, num := range nums {
        if num == candidate {
            occurrences++
        }
    }
    if occurrences > len(nums)/2 {
        return candidate
    }
    return -1
}

复杂度分析

  • 时间复杂度：$O(n)$。投票和验证各扫描一次数组。
  • 空间复杂度：$O(1)$。只维护候选、抵消余额和真实次数。

关键点总结

[!green]

  • 不同值抵消不会消除一个严格过半元素相对于其他值的数量优势。
  • 投票压缩的是尚未抵消的部分，count 不等于候选的总出现次数。
  • 第一趟负责缩小到唯一可能候选，第二趟负责证明它确实过半。

易错点总结

[!yellow]

  • 直接返回第一趟候选，会在不存在主要元素时给出错误答案。
  • 阈值必须严格大于一半，恰好一半不满足要求。
  • 第二趟应重新统计原数组中的真实次数，不能拿抵消后的 count 与一半比较。
  • 余额为零时可以更换候选，余额仍为正时不能随意替换当前候选。

相似题目

题目 难度 关联与区别
169. 多数元素 简单 原题保证多数元素存在，可直接返回候选；本题可能不存在，必须增加验证遍历。
229. 多数元素 II 中等 阈值降为三分之一后最多存在两个候选，推广投票还需要分别验证。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2026/21899656
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！