Boyer-Moore投票算法（多数元素问题）

问题描述
给定一个大小为 n 的数组，找出其中的“多数元素”。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。你可以假设数组是非空的，并且总是存在多数元素。例如，数组 [2,2,1,1,1,2,2] 的多数元素是 2，因为它出现了 4 次，而 ⌊ 7/2 ⌋ = 3，4 > 3。

解题思路
一种直观的方法是使用哈希表统计每个元素的出现次数，然后找出次数超过 n/2 的元素。这种方法的时间复杂度是 O(n)，空间复杂度也是 O(n)。但 Boyer-Moore 投票算法可以在 O(n) 时间复杂度和 O(1) 空间复杂度内解决这个问题，无需额外空间。

算法核心思想
算法的核心思想是“对消”。由于多数元素的出现次数超过一半，那么即使其他所有元素联合起来与多数元素进行一对一的“对消”，最后剩下的也一定是多数元素。

算法步骤详解

1. 初始化：设置一个候选者 candidate 和一个计数器 count。初始时，candidate 可以是任意值（通常设为第一个元素），count 设为 0。

2. 遍历数组：对于数组中的每一个元素 num：

   • 如果 count 为 0，说明当前没有候选者，或者之前的候选者已经被对消完了。此时，我们将当前元素 num 设为新的候选者，即 candidate = num，并将 count 设为 1。
   • 如果 count 不为 0：
     • 如果当前元素 num 等于候选者 candidate，说明遇到了“自己人”，那么 count 加 1。
     • 如果当前元素 num 不等于候选者 candidate，说明遇到了“敌人”，那么 count 减 1（相当于进行了一次对消）。

3. 返回结果：遍历结束后，candidate 中存储的就是多数元素。由于题目保证多数元素一定存在，所以可以直接返回 candidate。

举例说明
以数组 [2, 2, 1, 1, 1, 2, 2] 为例，演示算法过程：

• 初始：candidate = 2（第一个元素），count = 1。
• 遇到 2：与 candidate 相同，count 加 1 → count = 2。
• 遇到 1：与 candidate 不同，count 减 1 → count = 1。
• 遇到 1：与 candidate 不同，count 减 1 → count = 0（此时候选者 2 被对消完）。
• 遇到 1：count 为 0，设置新的候选者 candidate = 1，count = 1。
• 遇到 2：与 candidate 不同，count 减 1 → count = 0（候选者 1 被对消完）。
• 遇到 2：count 为 0，设置新的候选者 candidate = 2，count = 1。
• 遍历结束，多数元素是 candidate = 2。

算法正确性分析
由于多数元素的出现次数超过一半，它出现的次数比其他所有元素出现次数的总和还要多。因此，在遍历过程中，即使多数元素与其他元素不断对消，最终剩下的也一定是多数元素。

代码实现（Python）

def majorityElement(nums):
    candidate = None
    count = 0
    
    for num in nums:
        if count == 0:
            candidate = num
            count = 1
        elif num == candidate:
            count += 1
        else:
            count -= 1
            
    return candidate

总结
Boyer-Moore 投票算法通过巧妙的“对消”思想，在 O(n) 时间和 O(1) 空间内高效解决了多数元素问题。理解其核心在于把握“多数元素数量占优”这一关键条件，使得对消后必然剩下多数元素。