LC169　多数元素¶

简单通过率 67.3%python3核心代码模式技巧样例通过牛客 AC数组哈希表分治计数排序摩尔投票算法

讲解章节：哈希表

一句话

摩尔投票：让不同的元素两两同归于尽，活到最后的必是多数元素。

解题思路¶

这题考什么¶

多数元素的定义是出现次数严格大于 n / 2 向下取整，也就是说它比其余所有元素加起来还多。这个「过半」的条件强得离谱，可以直接抵消着用：

把数组里任意两个**不相等**的元素配成一对同时删掉。
每对最多消耗掉多数元素一个，同时至少消耗掉一个非多数元素，
多数元素与其余元素的数量差不会缩小到 0。
一直配到没法再配，剩下的元素必定全部相同，且就是多数元素。

摩尔投票（Boyer-Moore majority vote）是这个抵消过程的 O(1) 空间实现：维护一个候选 cand 与一个计票器 count。 count == 0 时，把当前元素立为新候选，count 置 1（开一局新的抵消）；当前元素等于候选，count += 1（支持票）；否则 count -= 1（一次「同归于尽」，抵掉一张候选的支持票）。

count 的含义不是「候选出现了多少次」，而是「候选比其他元素多出多少张票，在当前这一局里」。因为多数元素总票数过半，无论怎么分局抵消，它都不可能被彻底消完，最后留下的候选一定是它。

哈希表计数（O(n) 空间）与排序取中位数（O(n log n) 时间）也能做对，但都达不到进阶要求的「O(n) 时间 + O(1) 空间」。

数据规模与复杂度¶

1 <= n <= 5e4，-1e9 <= nums[i] <= 1e9，题面保证多数元素一定存在。时间 O(n)，一趟扫描；额外空间 O(1)，只有候选和计票器两个变量。

坑在哪¶

count 初值必须是 0，cand 的初值无所谓。count = 0 表示「当前没有候选，下一个元素直接立为候选」，第一轮循环就会把 nums[0] 立上，所以 cand 取什么都会被覆盖。若写成 cand = nums[0]、count = 1 再从下标 0 开始扫， nums[0] 会被计两票，抵消关系整体错位；那种写法必须配合从下标 1 开始扫，多一条边界约定，不如统一用 count = 0 起手，n == 1 的输入也自然正确。
必须先判 count == 0 再判是否等于候选。顺序写反的话，count 归零之后旧候选还留在 cand 里，下一个元素若恰好等于这个已被消完的旧候选，会被误算成支持票，抵消的分局边界就乱了。
本算法只在「多数元素确实存在」时正确。题面明确保证了这一点，所以不需要第二趟验证；若换成「可能不存在」的变体（如 LC229），必须再扫一遍数清候选的真实出现次数，否则会把一个随机元素当成答案返回。
count 递减到 0 就停，不要让它变成负数。判定写成 if count == 0 而不是 if count <= 0，是因为归零那一刻就立刻换候选，count 根本没有机会变负；但若把「换候选」误放在其他分支之后，就可能出现负计数，语义随之失效。
严格比对：多数元素唯一（两个不同的数不可能都超过半数），没有多解。

样例复核¶

nums = [2, 2, 1, 1, 1, 2, 2]，n = 7，多数元素需出现 > 3 次，2 出现 4 次。

x=2  count=0 -> 立候选 2，count=1
x=2  等于候选 -> count=2
x=1  不等 -> count=1
x=1  不等 -> count=0（候选 2 的票被消光，这一局结束）
x=1  count=0 -> 立候选 1，count=1
x=2  不等 -> count=0（又一局结束）
x=2  count=0 -> 立候选 2，count=1

最终候选是 2，与题面一致。中途候选一度变成 1，但只要多数元素票数过半，它总能在最后一局里活下来。

参考实现¶

solutions/leetcode/LC169/sol.py
from typing import List, Optional


class Solution:
    def majorityElement(self, nums: List[int]) -> int:
        # cand 是当前候选，count 是「候选在本局里比其他元素多出的票数」，
        # 不是候选的总出现次数。count 初值取 0 表示「尚无候选」，
        # 于是第一轮就会把 nums[0] 立为候选，n == 1 的输入也自然正确
        cand = 0
        count = 0
        for x in nums:
            # 先判归零：上一局已经两两抵消干净，从这里开一局新的。
            # 这一分支必须排在「是否等于候选」之前，否则被消完的旧候选
            # 还留在 cand 里，会把新元素误算成它的支持票
            if count == 0:
                cand = x
                count = 1
            elif x == cand:
                # 支持票
                count += 1
            else:
                # 一次「同归于尽」：一张反对票抵掉一张候选的支持票。
                # 每次抵消至多消耗多数元素一个，所以它的领先量不会被抹平。
                # count 减到 0 就由上面的分支换人，永远不会变成负数
                count -= 1
        # 题面保证多数元素存在，抵消到最后活下来的候选就是它，无需二次验证
        return cand

LC169 多数元素¶