寻找数组中的众数（Boyer-Moore 投票算法） 题目描述 给定一个大小为 n 的数组 nums，请找出其中出现次数超过 ⌊n/2⌋ 的元素（即众数）。假设数组非空，且众数一定存在。 解题思路 常规解法可能使用哈希表统计频率，但需要 O(n) 额外空间。Boyer-Moore 投票算法可以在 O(1) 空间内解决该问题。其核心思想是通过 抵消 策略：将众数视为“支持票”，其他数视为“反对票”，由于众数数量超过一半，最终剩下的候选人一定是众数。 步骤详解 初始化候选人及其计数器 设置候选人 candidate 为任意值（如 nums[ 0]），计数器 count 初始为 0。 遍历数组执行投票 若 count == 0 ，说明当前无候选人，将当前数字设为新候选人（ candidate = nums[i] ）。 若当前数字等于候选人，则增加支持（ count++ ）；否则减少支持（ count-- ），相当于抵消一票。 算法正确性解释 由于众数出现次数超过一半，即使所有其他数联合抵消众数的票，最终剩余票数仍为正数，候选人必为众数。 例如 nums = [ 2,2,1,1,1,2,2 ]： 遍历至 2：candidate=2, count=1 遍历至 2：candidate=2, count=2 遍历至 1：candidate=2, count=1（抵消） 遍历至 1：candidate=2, count=0（抵消） 遍历至 1：count=0 → candidate=1, count=1 遍历至 2：candidate=1, count=0（抵消） 遍历至 2：count=0 → candidate=2, count=1 最终候选人 2 即为众数。 边界情况处理 题目已假设众数存在，无需验证结果。若未假设，需二次遍历确认候选人是否真为众数。 复杂度分析 时间复杂度：O(n)，仅遍历数组一次。 空间复杂度：O(1)，仅使用两个变量。