如何找出数组中出现次数超过一半的元素？

直接回答：用 Boyer-Moore 投票算法。维护一个候选值 candidate 和计数 count：遍历时若 count 为 0 就把当前元素设为候选；当前元素等于候选则 count+1，否则 count−1。因为众数出现次数超过一半，它与所有非众数「一一抵消」后必有剩余，遍历结束候选即众数。时间 O(n)，空间 O(1)。

展开解析：直观理解是把「一个众数 + 一个非众数」配对丢弃，众数过半保证丢不完。注意前提：题目必须保证众数存在，否则最后要再扫一遍验证候选真的过半。对比其他思路：排序取中位 O(n log n)、哈希计数 O(n) 空间，都不如投票法。经典扩展是「出现次数超过 n/3 的元素」：超过三分之一的数至多两个，用两个候选、两个计数做三路抵消，最后分别验证两个候选的真实出现次数。追问方向：为什么 n/3 时最多两个答案、投票算法与多数派在分布式共识中的类比（都只是思想类比，协议本身不靠它）。

示例：

def majority_element(nums):
    candidate, count = None, 0
    for x in nums:
        if count == 0:
            candidate = x
        count += 1 if x == candidate else -1
    return candidate