BM51　数组中出现次数超过一半的数字¶

简单通过率 33.6%python3核心代码模式样例通过牛客 AC数组哈希

牛客原题　源码

讲解章节：哈希表

一句话

摩尔投票：不同就同归于尽，活到最后的就是众数。

解题思路¶

这题考什么¶

摩尔投票法（Boyer-Moore majority vote），用一个候选加一个计数器完成 O(1) 空间统计。

把数组看成一场混战：相同数字是队友，不同数字互相抵消。维护当前擂主 cand 与它的票数 count：

count == 0        擂主被打空，换人：cand = x, count = 1
x == cand         队友来了：count 加一
x != cand         同归于尽：count 减一

正确性：每次「同归于尽」都消掉一个众数和一个非众数。众数出现次数超过 n/2，比其余所有数字加起来还多，配对消完之后剩下的只能是众数，它必然占着最后的擂主位。

数据规模与复杂度¶

n <= 50000，元素取值 0 到 10000，时限其他语言 2 秒。投票法一遍扫描，时间 O(n)、空间 O(1)，两项都踩在题面要求上。对照：哈希计数是 O(n) 时间但 O(n) 空间；排序取中位数是 O(n log n)；利用值域开一个长度 10001 的计数数组也能 O(n)，但空间是 O(值域)，题面要求的 O(1) 只有投票法满足。

坑在哪¶

cand 在扫描途中可能是错的，只有扫完全程的结果才有意义。下表第 3 步擂主还是 1，此时提前返回就错了：

[1, 2, 3, 2, 2, 2, 5, 4, 2] x: 1 2 3 2 2 2 5 4 2 cand: 1 1 1 2 2 2 2 2 2 count: 1 0 1 0 1 2 1 0 1 -> 2
count == 0 必须是第一个判的分支。若先判 x == cand，票数归零后的旧擂主还能继续接收自己的票，抵消关系被破坏，答案不再可靠。
count 的初值只能是 0。若写成 cand = 0、count = 1，等于凭空给值 0 送了一票： [1, 1, 0, 0, 1] 里众数是 1（5 个里占 3 个），带着这一票跑完会返回 0。初值 0 则第一个元素立刻触发换人，cand 的初值取什么都无所谓。
省掉第二遍验证的前提是题面的「保证有解」。若换成「可能不存在众数」的变体，必须再扫一遍数出 cand 的真实次数，确认它超过 n/2 才能返回。

样例复核¶

上表最后一列 cand = 2，与样例输出一致：数字 2 在 9 个元素里出现 5 次。

参考实现¶

solutions/nowcoder/BM51/sol.py
from typing import List, Optional


class Solution:
    def MoreThanHalfNum_Solution(self, numbers: List[int]) -> int:
        # count 初值必须是 0：第一个元素立刻触发换人，cand 的初值才不会被当成一票
        cand = 0
        count = 0
        for x in numbers:
            # 三个分支的顺序不能改：先判票数归零，再判是不是队友
            if count == 0:              # 擂主被打空，换人
                cand = x
                count = 1
            elif x == cand:
                count += 1              # 队友，加一票
            else:
                count -= 1              # 对手，同归于尽
        # 中途的 cand 没有意义，扫完全程才是答案；题目保证有解，无需第二遍校验
        return cand

BM51 数组中出现次数超过一半的数字¶