Boyer-Moore 投票算法：高效发现多数元素的艺术

Boyer-Moore 投票算法：高效发现多数元素的艺术

Boyer-Moore 投票算法，一种在数据科学领域中备受推崇的算法，以其寻找数组中“多数元素”的高效能力而闻名。所谓“多数元素”，是指在给定数组中出现次数超过一半的元素。这种算法由 Robert S. Boyer 和 J Strother Moore 两位杰出的计算机科学家在 1981 年提出，自那以后，它便以其简洁而强大的特性，成为了解决实际问题中不可或缺的工具。

算法原理：巧妙的投票机制

Boyer-Moore 投票算法的核心思想是巧妙而高效的。它通过两次遍历数组的过程，首先找出一个可能是多数元素的候选人，然后在第二次遍历中验证这个候选人是否真的是多数元素。Boyer-Moore 投票算法的巧妙之处在于，它只使用了一个计数器就实现了对潜在的多数元素的追踪，并且能够在遍历数组的过程中动态地调整候选人。

在第一次遍历中，算法初始化一个计数器和一个候选元素。每当遇到一个新的元素，如果计数器为零，它就将这个元素设为当前的候选人。如果遇到的元素与当前的候选人相同，计数器就增加；如果不同，计数器就减少。这样，当第一次遍历结束时，计数器不为零的情况下，当前的候选人就是数组中的一个潜在多数元素。

第二次遍历则是为了验证这个候选人是否真的是多数元素。算法会重新计数这个候选人在数组中出现的次数。如果这个次数超过了数组长度的一半，那么这个候选人就是多数元素；如果没有，那么数组中不存在多数元素。

实现代码

Boyer-Moore 投票算法的 Python 实现代码：

def majority_element(nums):
    candidate = None
    count = 0

    # 第一遍遍历，找到候选人
    for num in nums:
        if count == 0:
            candidate = num
            count = 1
        elif num == candidate:
            count += 1
        else:
            count -= 1

    # 第二遍遍历，验证候选人
    count = 0
    for num in nums:
        if num == candidate:
            count += 1

    if count > len(nums) // 2:
        return candidate
    else:
        return None

Boyer-Moore 投票算法的 C 实现代码：

int majority_element(int* nums, int numsSize) {
    int candidate = 0;
    int count = 0;

    // 第一遍遍历，找到候选人
    for (int i = 0; i < numsSize; i++) {
        if (count == 0) {
            candidate = nums[i];
            count = 1;
        } else if (nums[i] == candidate) {
            count++;
        } else {
            count--;
        }
    }

    // 第二遍遍历，验证候选人
    count = 0;
    for (int i = 0; i < numsSize; i++) {
        if (nums[i] == candidate) {
            count++;
        }
    }

    if (count > numsSize / 2) {
        return candidate;
    } else {
        return -1;
    }
}

算法分析

• 时间复杂度：O(n)
• 空间复杂度：O(1)

变体问题：寻找前 k 个多数元素

在某些情况下，我们可能需要找到数组中出现次数超过 n/k 的所有元素，其中 n 是数组的长度，k 是一个给定的整数。这种情况下，可以使用 Boyer-Moore 投票算法的多候选人版本。

算法步骤：

1. 初始化 k 个候选人和 k 个计数器。

2. 遍历数组，对于每个元素num：

   • 如果 num 是当前的候选人之一，增加对应的计数器。
   • 如果 num 不是当前的候选人之一，并且有空闲的候选人位置，将 num 添加为新的候选人，并将对应的计数器设置为 1。
   • 如果 num 不是当前的候选人之一，并且没有空闲的候选人位置，减少所有候选人的计数器。

3. 遍历结束后，验证所有候选人的计数器是否超过 n/k，找出所有满足条件的候选人。

变体问题的 Python 实现代码：

def majority_elements(nums, k):
    if k < 2:
        return []

    # 初始化候选人和计数器
    candidates = {}
    for num in nums:
        if num in candidates:
            candidates[num] += 1
        elif len(candidates) < k - 1:
            candidates[num] = 1
        else:
            for key in list(candidates.keys()):
                candidates[key] -= 1
                if candidates[key] == 0:
                    del candidates[key]

    # 验证候选人
    counts = {key: 0 for key in candidates}
    for num in nums:
        if num in counts:
            counts[num] += 1

    result = []
    for key, count in counts.items():
        if count > len(nums) // k:
            result.append(key)

    return result

LeeCode相关题目：
169. 多数元素
229. 多数元素 II
2404. 出现最频繁的偶数元素
1287. 有序数组中出现次数超过25%的元素