摩尔投票算法（Boyer-Moore Majority Vote Algorithm）
是一种用于在数据序列中高效找出出现次数超过一定比例的元素的算法，尤其擅长在常数级空间复杂度（O(1)）和线性时间复杂度（O(n)） 内解决问题。
算法要解决什么问题
摩尔投票算法最经典的应用场景是：在一个长度为 n 的数组中找到那个出现次数严格大于 ⌊n/2⌋ 的元素（即多数元素）。算法基于一个重要的前提假设：这样的多数元素必须存在。如果这个前提不满足，算法找到的"候选者"可能并非真正的多数元素，因此在实际应用中，有时需要额外进行一次遍历来验证候选者是否确实满足条件。
算法的核心思想
摩尔投票法的核心思想非常巧妙，可以概括为 “相互抵消” 。其基本思路是每次从序列中选择两个不同的元素进行“配对”或“抵消”，由于多数元素的数量超过总数的一半，那么无论其他元素如何组合，最终剩下的一定是多数元素。
这个过程可以借助一个生动的比喻来理解：想象一场诸侯争霸游戏，假设你方人口超过总人口一半以上，并且能保证每个人口出去干仗都能一换一。即使所有其他国家都联合起来对付你，只要你们内部不互相攻击，最终活下来的必定是你方的人
算法的运作步骤
在具体实现上，算法通常通过维护一个候选元素（candidate） 和一个计数器（count） 来完成：
初始化：将候选元素 candidate设置为一个初始值（如数组的第一个元素），计数器 count设置为 0 或 1。
遍历序列：对于序列中的每一个元素：
如果 count为 0，则将当前元素设为新的 candidate，并令 count = 1。
如果当前元素等于 candidate，则 count加 1（可以视为支持候选者的力量增强了）。
如果当前元素不等于 candidate，则 count减 1（可以理解为两个不同的元素进行了一次抵消）。
确定结果：遍历结束后，candidate中存储的元素就是我们要找的多数元素（在保证多数元素存在的前提下）
给定一个大小为 n的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
示例 1：
输入：nums = [3,2,3]输出：3
示例 2：
输入：nums = [2,2,1,1,1,2,2]输出：2
n == nums.length1 <= n <= 5 * 104-109 <= nums[i] <= 109
进阶：尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。
要在线性时间O(n)和常数空间O(1)内解决这个问题，是最佳选择。它巧妙利用"多数元素出现次数超过一半"的特性，通过元素间的"抵消"思想高效解决问题。
算法思路
摩尔投票算法的核心在于抵消机制：将多数元素与其他元素进行配对抵消。由于多数元素的数量超过总数的一半，最终剩下的必然是多数元素。
具体来说，算法维护一个"候选元素"和"计数器"：
遍历数组，当前元素与候选元素相同则计数器加1，不同则减1
当计数器归零时，更新候选元素为当前元素
由于多数元素数量优势，它最终会成为留在擂台上的"候选者"
def majorityElement(nums): """ 使用摩尔投票算法寻找多数元素 参数: 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# 测试示例if __name__ == "__main__": # 示例1 nums1 = [3, 2, 3] print(f"示例1: nums = {nums1}") print(f"输出: {majorityElement(nums1)}") # 应输出3 # 示例2 nums2 = [2, 2, 1, 1, 1, 2, 2] print(f"示例2: nums = {nums2}") print(f"输出: {majorityElement(nums2)}") # 应输出2
算法演示
以示例[2, 2, 1, 1, 1, 2, 2]为例：
步骤 | 当前元素 | candidate | count | 操作说明 |
|---|
初始 | - | None | 0 | 初始化 |
1 | 2 | 2 | 1 | count=0，设置candidate=2 |
2 | 2 | 2 | 2 | 相同元素，count+1 |
3 | 1 | 2 | 1 | 不同元素，count-1 |
4 | 1 | 2 | 0 | 不同元素，count-1（归零） |
5 | 1 | 1 | 1 | count=0，设置candidate=1 |
6 | 2 | 1 | 0 | 不同元素，count-1（归零） |
7 | 2 | 2 | 1 | count=0，设置candidate=2 |
最终返回多数元素：2
复杂度分析
时间复杂度：O(n)，只需遍历数组一次
空间复杂度：O(1)，只使用两个额外变量
其他解法对比
虽然哈希表法也具备O(n)时间复杂度，但需要O(n)的额外空间；排序法虽然空间复杂度为O(1)，但时间复杂度为O(n log n)。摩尔投票算法在时间和空间上都是最优解。
算法扩展
摩尔投票算法可以推广到找出出现次数超过n/k的所有元素的情况，只需维护k-1个候选元素和计数器即可。
这种方法高效且优雅，是处理"多数元素"类问题的经典算法。
import unittestdef majorityElement(nums): """ 使用摩尔投票算法寻找多数元素 参数: 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 candidateclass TestMajorityElement(unittest.TestCase): """测试多数元素查找算法""" def test_leetcode_example1(self): """测试LeetCode示例1""" self.assertEqual(majorityElement([3, 2, 3]), 3) def test_leetcode_example2(self): """测试LeetCode示例2""" self.assertEqual(majorityElement([2, 2, 1, 1, 1, 2, 2]), 2) def test_single_element(self): """测试单元素数组""" self.assertEqual(majorityElement([5]), 5) self.assertEqual(majorityElement([0]), 0) self.assertEqual(majorityElement([-3]), -3) def test_all_same_elements(self): """测试所有元素相同的情况""" self.assertEqual(majorityElement([7, 7, 7, 7, 7]), 7) self.assertEqual(majorityElement([1, 1, 1]), 1) def test_negative_numbers(self): """测试包含负数的数组""" self.assertEqual(majorityElement([-1, -1, -2]), -1) self.assertEqual(majorityElement([-3, 1, 1, -3, 1]), 1) def test_large_range(self): """测试数值范围较大的情况""" self.assertEqual(majorityElement([100, 50, 100, 100, 25]), 100) self.assertEqual(majorityElement([-1000, 500, -1000, -1000]), -1000) def test_alternating_pattern(self): """测试交替模式""" self.assertEqual(majorityElement([1, 2, 1, 2, 1]), 1) self.assertEqual(majorityElement([3, 4, 4, 3, 3, 4, 3]), 3) def test_algorithm_correctness(self): """验证算法正确性（多种情况对比）""" test_cases = [ # (输入数组, 期望结果, 描述) ([3, 2, 3], 3, "LeetCode示例1"), ([2, 2, 1, 1, 1, 2, 2], 2, "LeetCode示例2"), ([1], 1, "单元素数组"), ([5, 5, 3], 5, "简单多数"), ([1, 2, 3, 2, 2, 2, 5], 2, "复杂分布"), ] for nums, expected, description in test_cases: with self.subTest(nums=nums, description=description): actual = majorityElement(nums) self.assertEqual(actual, expected, f"Failed for {description}")def run_comprehensive_test_suite(): """运行全面测试并生成详细报告""" # 创建测试加载器 loader = unittest.TestLoader() # 创建测试套件 suite = unittest.TestSuite() suite.addTests(loader.loadTestsFromTestCase(TestMajorityElement)) # 运行测试 runner = unittest.TextTestRunner(verbosity=2) result = runner.run(suite) # 生成测试报告 print("\n" + "="*60) print("多数元素算法测试报告") print("="*60) print(f"运行测试数: {result.testsRun}") print(f"失败数: {len(result.failures)}") print(f"错误数: {len(result.errors)}") if result.wasSuccessful(): print("🎉 所有测试通过！算法实现正确。") # 显示关键测试用例验证 print("\n关键测试用例验证:") key_test_cases = [ ([3, 2, 3], 3, "LeetCode示例1"), ([2, 2, 1, 1, 1, 2, 2], 2, "LeetCode示例2"), ([1], 1, "单元素数组"), ([7, 7, 7, 7, 7], 7, "全相同元素"), ] for nums, expected, description in key_test_cases: actual = majorityElement(nums) status = "✅" if actual == expected else "❌" print(f"{description:15} | 输入: {nums}") print(f"{'':15} | 输出: {actual} (期望: {expected}) {status}") print("-" * 50) else: print("❌ 有测试失败，请检查算法实现。") # 输出失败详情 for test, traceback in result.failures + result.errors: print(f"\n失败测试: {test}") print(f"错误信息:\n{traceback}") return result.wasSuccessful()if __name__ == '__main__': # 运行全面测试 success = run_comprehensive_test_suite() # 退出代码 exit(0 if success else 1)
测试说明
测试覆盖范围
这个测试脚本全面覆盖了多数元素查找算法的各种场景：
基础功能测试：
LeetCode官方示例验证
单元素数组处理
所有元素相同的特殊情况
边界条件测试：
算法正确性测试：
运行方式
# 方式1：直接运行测试脚本python test_majority_element.py# 方式2：运行特定测试类python -m unittest test_majority_element.TestMajorityElement# 方式3：运行单个测试方法python -m unittest test_majority_element.TestMajorityElement.test_leetcode_example1# 方式4：详细模式运行python -m unittest test_majority_element.py -v
测试设计特点
子测试支持：使用 subTest进行参数化测试，避免一个失败导致整个测试类停止
详细报告：运行后生成清晰的测试摘要和关键用例验证
退出代码：根据测试结果返回适当的退出代码，便于CI/CD集成
算法核心验证
测试特别关注摩尔投票算法的正确性：
抵消机制：验证算法正确处理元素间的抵消逻辑
候选更新：测试计数器归零时的候选元素更新
多数元素特性：确保最终返回的元素确实出现超过半数
这个测试套件可以确保您的 majorityElement函数在各种情况下都能正确工作
互动：实践出真知，多复盘，多敲代码
10个月宝宝每天需要喝多少奶粉？
