使用 Boyer-Moore 投票算法找出数组中的多数元素

问题描述

给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。你可以假设数组是非空的，并且给定的数组总是存在多数元素。

示例 1：

输入：nums = [3,2,3]
输出：3

示例 2：

输入：nums = [2,2,1,1,1,2,2]
输出：2

提示：

• n == nums.length
• 1 <= n <= 5 * 10^4
• -10^9 <= nums[i] <= 10^9

进阶：尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。

Boyer-Moore 投票算法

该算法的核心思想是通过两个变量 candidate 和 count 来跟踪当前的候选多数元素及其出现次数。具体步骤如下：

1. 初始化 candidate 为 None，count 为 0。
2. 遍历数组 nums 中的每个元素 num：
   • 如果 count 为 0，则将 candidate 设置为当前元素 num，并将 count 设置为 1。
   • 如果 count 不为 0，且当前元素 num 等于 candidate，则将 count 增加 1。
   • 如果 count 不为 0，且当前元素 num 不等于 candidate，则将 count 减少 1。
3. 最终，candidate 即为多数元素。

代码实现

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

# 示例测试
print(majorityElement([3, 2, 3]))  # 输出: 3
print(majorityElement([2, 2, 1, 1, 1, 2, 2]))  # 输出: 2

详细模拟过程

假设我们有一个数组 nums = [2, 2, 1, 1, 1, 2, 2]，我们将用 Boyer-Moore 投票算法来找出其中的多数元素。

步骤

1. 初始化 candidate 为 None，count 为 0。
2. 遍历数组 nums 中的每个元素 num。

详细模拟过程

• 初始状态:
  candidate = None
count = 0
• 第1次迭代 (num = 2):
  count = 0，所以将 candidate 设置为 2，count 设置为 1。
  状态更新为：
  candidate = 2
count = 1
• 第2次迭代 (num = 2):
  num 等于 candidate，所以将 count 增加 1。
  状态更新为：
  candidate = 2
count = 2
• 第3次迭代 (num = 1):
  num 不等于 candidate，所以将 count 减少 1。
  状态更新为：
  candidate = 2
count = 1
• 第4次迭代 (num = 1):
  num 不等于 candidate，所以将 count 减少 1。
  状态更新为：
  candidate = 2
count = 0
• 第5次迭代 (num = 1):
  count = 0，所以将 candidate 设置为 1，count 设置为 1。
  状态更新为：
  candidate = 1
count = 1
• 第6次迭代 (num = 2):
  num 不等于 candidate，所以将 count 减少 1。
  状态更新为：
  candidate = 1
count = 0
• 第7次迭代 (num = 2):
  count = 0，所以将 candidate 设置为 2，count 设置为 1。
  状态更新为：
  candidate = 2
count = 1

最终结果

遍历完成后，candidate 为 2，即为数组中的多数元素。

总结

通过这个模拟过程，我们可以看到 Boyer-Moore 投票算法如何在一次遍历中确定多数元素。由于多数元素的出现次数大于数组长度的一半，因此最终 candidate 一定是多数元素。

通过这种方式，我们可以高效地找到数组中的多数元素。