摩尔投票算法

摩尔投票算法最早由 Robert S. Boyer 和 J Strother Moore 在 1981 年的论文 “MJRTY—A Fast Majority Vote Algorithm” 中提出。这篇论文描述了摩尔投票算法的原理和证明，并展示了它在实际应用中的高效性。

论文的引用信息如下：

Title: MJRTY—A Fast Majority Vote Algorithm

Authors: Robert S. Boyer, J Strother Moore

Year: 1981 Published in: Automated

Reasoning: Essays in Honor of Woody Bledsoe

Publisher: Springer-Verlag

Pages: 105-117

算法思想

摩尔投票算法（Moore‘s Voting Algorithm）是一种用于在数组中寻找多数元素的有效方法。所谓的多数元素就是在数组中出现次数超过一半以上的元素。所以经常用于众数的查找。

摩尔投票算法的基本思想：是通过消除不同元素之间的对抗来找到可能的多数元素，所以算法遍历数组只需要维护两个变量，分别是候选元素和其对应的票数。开始时，候选元素为空，票数为0，然后对数组中的每个元素，执行以下步骤：

1.如果票数为0，将当前元素设为候选元素，并将票数设为1。

2.如果元素等于候选元素，则票数加1。

3.如果当前元素不等于候选元素，则票数减一。

这样做的原因是，相同元素的票数会相互抵消，不同元素的对抗也会导致票数减少。由于多数元素的条件是出现次数超过一半以上，所以最终留下的候选元素就很有可能是多数元素。

以下是摩尔投票的C++伪代码：

function findMajorityElement(nums):candidate = Nonecount = 0for num in nums:if count == 0:candidate = numif candidate == num:count += 1else:count -= 1# 进行第二次遍历，验证 candidate 是否为多数元素count = 0for num in nums:if num == candidate:count += 1if count > len(nums) / 2:return candidateelse:return None

摩尔投票算法的时间复杂度为O(n)，空间复杂度为O(1)，是一种高效的寻找多数元素的算法。

题目概述

解题代码

C++解题代码如下：

class Solution {
public:int majorityElement(vector<int>& nums) {//多数元素是指在数组中出现大于n/2的次数int candidate, count = 0;for(auto num : nums) {if(count == 0) candidate = num;if(num == candidate) count++;else count--;}return candidate;}
};

Java解题代码如下：

 public static int majorityElement(int[] nums) {//多数元素是指在数组中出现大于n/2的次数int x = nums[0];int count = 0;for (int i = 0; i < nums.length; ++i) {if (count == 0) {x = nums[i];}if (nums[i] == x) {count++;} else {count--;}}return x;}

上述解题的时间复杂度为O(n)