摩尔投票算法原理实现一文剖析-海口c网

摩尔投票算法原理实现一文剖析

article/2025/6/19 4:51:09

摩尔投票算法原理&实现一文剖析

- 一、算法原理
- - 1.1 基本思想
  - 1.2 数学原理
- 二、算法实现
- - 2.1 Python实现
  - 2.2 Java实现
  - 2.3 C++实现
- 三、复杂度分析
- 四、应用场景
- - 4.1 多数元素问题
  - 4.2 扩展应用：寻找出现次数超过n/3的元素
- 五、算法优势与注意事项
- - 5.1 优势
  - 5.2 注意事项
- 总结

摩尔投票法（Boyer-Moore Voting Algorithm）是一种高效的算法，主要用于在数组中寻找出现次数超过一半的元素，即多数元素。该算法由Robert S. Boyer和J Strother Moore在1981年提出，其时间复杂度为O(n)，空间复杂度为O(1)，是处理这类问题的最优解法。本文我将为你详细介绍摩尔投票法的原理、实现及应用场景。

一、算法原理

1.1 基本思想

摩尔投票法的核心思想是基于这样一个观察：如果一个元素在数组中出现次数超过一半，那么该元素的出现次数一定比其他所有元素的出现次数总和还要多。

算法通过维护两个变量来实现：

候选元素（candidate）：记录当前可能的多数元素
计数（count）：记录候选元素的相对出现次数

算法的执行过程可以分为两个阶段：

投票阶段：遍历数组，对每个元素进行投票。如果当前元素与候选元素相同，则计数加1；否则计数减1。当计数减为0时，更换候选元素为当前元素，并将计数重置为1。
验证阶段：遍历结束后，得到的候选元素需要再次验证是否真的出现次数超过一半（在某些题目中，可能需要这一步骤，但在明确存在多数元素的情况下可以省略）。

1.2 数学原理

假设数组长度为n，多数元素出现次数为m（m > n/2）。在投票过程中，每当遇到一个非候选元素时，计数减1，但由于多数元素的出现次数超过一半，即使每次遇到非候选元素都抵消一次，最终候选元素的计数仍会大于0。因此，最终得到的候选元素必然是多数元素。
摩尔投票法

二、算法实现

2.1 Python实现

def majorityElement(nums):"""摩尔投票法实现，寻找数组中出现次数超过一半的元素"""# 初始化候选元素和计数candidate = Nonecount = 0# 投票阶段for num in nums:if count == 0:# 当计数为0时，更换候选元素为当前元素candidate = numcount = 1elif num == candidate:# 当前元素与候选元素相同，计数加1count += 1else:# 当前元素与候选元素不同，计数减1count -= 1# 验证阶段（在明确存在多数元素的情况下可以省略）# 这里简单验证候选元素的出现次数是否超过一半count = 0for num in nums:if num == candidate:count += 1if count > len(nums) // 2:return candidateelse:return None  # 实际上题目保证存在多数元素，不会执行到这一步# 示例用法
nums = [2, 2, 1, 1, 1, 2, 2]
print("多数元素是:", majorityElement(nums))  # 输出: 2

2.2 Java实现

public class BoyerMooreVoting {public static int majorityElement(int[] nums) {// 初始化候选元素和计数int candidate = 0;int count = 0;// 投票阶段for (int num : nums) {if (count == 0) {candidate = num;count = 1;} else if (num == candidate) {count++;} else {count--;}}// 验证阶段（在明确存在多数元素的情况下可以省略）count = 0;for (int num : nums) {if (num == candidate) {count++;}}if (count > nums.length / 2) {return candidate;} else {return -1;  // 实际上题目保证存在多数元素，不会执行到这一步}}public static void main(String[] args) {int[] nums = {2, 2, 1, 1, 1, 2, 2};System.out.println("多数元素是: " + majorityElement(nums));  // 输出: 2}
}

2.3 C++实现

#include <iostream>
#include <vector>
using namespace std;int majorityElement(vector<int>& nums) {// 初始化候选元素和计数int candidate = 0;int count = 0;// 投票阶段for (int num : nums) {if (count == 0) {candidate = num;count = 1;} else if (num == candidate) {count++;} else {count--;}}// 验证阶段（在明确存在多数元素的情况下可以省略）count = 0;for (int num : nums) {if (num == candidate) {count++;}}if (count > nums.size() / 2) {return candidate;} else {return -1;  // 实际上题目保证存在多数元素，不会执行到这一步}
}int main() {vector<int> nums = {2, 2, 1, 1, 1, 2, 2};cout << "多数元素是: " << majorityElement(nums) << endl;  // 输出: 2return 0;
}

三、复杂度分析

时间复杂度：O(n)，算法只需遍历数组两次（投票阶段一次，验证阶段一次），每次遍历的时间复杂度均为O(n)。
空间复杂度：O(1)，只需要常数级的额外空间来存储候选元素和计数。

四、应用场景

4.1 多数元素问题

摩尔投票法最典型的应用是解决LeetCode上的"多数元素"问题（题目编号169）：给定一个大小为n的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于⌊n/2⌋的元素。

4.2 扩展应用：寻找出现次数超过n/3的元素

摩尔投票法可以扩展用于寻找数组中出现次数超过n/3的元素（LeetCode题目编号229）。此时需要维护两个候选元素和对应的计数，基本思想类似，但在投票阶段需要更复杂的逻辑处理。

def majorityElement(nums):"""寻找数组中出现次数超过n/3的元素"""if not nums:return []# 初始化两个候选元素和计数candidate1, candidate2 = None, Nonecount1, count2 = 0, 0# 投票阶段for num in nums:if num == candidate1:count1 += 1elif num == candidate2:count2 += 1elif count1 == 0:candidate1 = numcount1 = 1elif count2 == 0:candidate2 = numcount2 = 1else:count1 -= 1count2 -= 1# 验证阶段result = []threshold = len(nums) // 3for candidate in [candidate1, candidate2]:if nums.count(candidate) > threshold:result.append(candidate)return result# 示例用法
nums = [3, 2, 3]
print("出现次数超过n/3的元素:", majorityElement(nums))  # 输出: [3]