2013 年第 41 题

题目描述

给定一个长度为 n 的整型数组，若其中存在一个元素出现次数严格大于 n / 2，则称该元素为主元素。请设计一个尽可能高效的算法找出数组中的主元素；若不存在，则返回不存在。

解题思路

最优思路是摩尔投票法。

核心结论：

• 若主元素存在，它和其他所有元素两两抵消后，最后剩下的一定还是它。

算法过程：

1. 维护候选值 candidate 和计数器 count。
2. count == 0 时，当前元素成为新的候选值。
3. 若当前元素等于候选值，count += 1；否则 count -= 1。
4. 第一趟结束后得到一个候选值，但它不一定真的超过一半。
5. 再扫描一遍，验证它的出现次数是否真的大于 n / 2。

手算示例

数组：[0, 5, 5, 3, 5, 7, 5, 5]

candidate=0, count=0

读到 0：candidate=0, count=1
读到 5：不同，count=0
读到 5：candidate=5, count=1
读到 3：不同，count=0
读到 5：candidate=5, count=1
读到 7：不同，count=0
读到 5：candidate=5, count=1
读到 5：相同，count=2

候选值为 5
再统计一次，5 共出现 5 次，5 > 8/2
所以主元素是 5

Python 实现

def majority_element(nums):
    if not nums:
        return None

    candidate = None
    count = 0

    for x in nums:
        if count == 0:
            candidate = x
            count = 1
        elif x == candidate:
            count += 1
        else:
            count -= 1

    if nums.count(candidate) > len(nums) // 2:
        return candidate
    return None

复杂度分析

• 时间复杂度：O(n)
• 空间复杂度：O(1)

易错点

• 第一趟投票只能得到候选值，不能直接返回。
• 真题不保证主元素一定存在，所以必须二次验证。
• “超过一半”是严格大于 n / 2，不是大于等于。

对应题

来源	题目	相似度	主要差异
LeetCode	169. 多数元素	90%	该题默认一定存在主元素
剑指 Offer	39. 数组中出现次数超过一半的数字	90%	该题默认一定存在主元素
程序员面试金典	17.10. 主要元素	100%	题意基本一致

难度

⭐️⭐️⭐️⭐️