Boyer-Moore 多数投票算法

功能说明

多数投票算法用配对抵消的思路在一次遍历中找出最可能的多数元素：不同值相互抵消，最后剩下的候选值再单独计数校验。它适合日志流、投票统计、监控事件聚合这类数据量大且内存受限的场景，不需要哈希表保存全部频次。

示例同时给出扩展版本 elements_over_third：维护两个候选和两个计数器，可以找出所有出现次数严格超过三分之一的元素，最多只有两个结果。

关键代码

majority_candidate 在 balance 归零时替换候选值，随后相同值加一、不同值减一。majority_element 必须再次遍历统计候选值票数，只有严格大于长度一半才返回，否则返回 None，这一步是防止无多数时误报的关键。elements_over_third 对两个候选分别计数，遇到第三个不同值就同时减一；最后对两个候选做真实计数，过滤掉不超过三分之一的项。

使用注意

比较使用相等运算符，元素必须可哈希或至少支持相等比较；字典、列表等可变对象不适合直接比较。空序列返回 None 或空列表。算法只保证候选值正确，不能跳过校验步骤。对于出现次数刚好等于一半的情况，规则要求严格多数，因此返回 None。序列需要支持 len 和 count；生成器请先转成列表。浮点数参与投票时要注意 NaN 不等于自身，会破坏计数。

验证方式

五张选票中有三张投给 ada，输出 winner 为 ada；只有 a 和 b 各一票时输出 None，说明校验生效。序列 x, x, y, y, z, x 中 x 出现三次，超过 6 的三分之一，因此结果为 x，y 只有两次不会入选。可以追加测试确认空列表和全相同值的边界行为。

代码示例

from collections.abc import Sequence
from typing import TypeVar

T = TypeVar("T")


def majority_candidate(values: Sequence[T]) -> T | None:
    candidate: T | None = None
    balance = 0
    for value in values:
        if balance == 0:
            candidate = value
            balance = 1
        elif value == candidate:
            balance += 1
        else:
            balance -= 1
    return candidate


def majority_element(values: Sequence[T]) -> T | None:
    if not values:
        return None
    candidate = majority_candidate(values)
    if candidate is None:
        return None
    votes = sum(1 for value in values if value == candidate)
    return candidate if votes > len(values) // 2 else None


def elements_over_third(values: Sequence[T]) -> list[T]:
    if not values:
        return []
    first: T | None = None
    second: T | None = None
    count_first = 0
    count_second = 0
    for value in values:
        if first is not None and value == first:
            count_first += 1
        elif second is not None and value == second:
            count_second += 1
        elif count_first == 0:
            first, count_first = value, 1
        elif count_second == 0:
            second, count_second = value, 1
        else:
            count_first -= 1
            count_second -= 1
    limit = len(values) // 3
    return [
        item
        for item in (first, second)
        if item is not None and values.count(item) > limit
    ]


def main() -> None:
    ballots = ["ada", "bob", "ada", "ada", "cy"]
    print("winner:", majority_element(ballots))
    print("no majority:", majority_element(["a", "b"]))
    print("over a third:", elements_over_third(["x", "x", "y", "y", "z", "x"]))

    records = [
        {"team": "red"},
        {"team": "blue"},
        {"team": "red"},
        {"team": "red"},
    ]
    print("red votes:", majority_element([record["team"] for record in records]))


if __name__ == "__main__":
    main()