算法学习笔记：169. 多数元素——摩尔投票算法（Moore‘s Voting Algorithm）

摩尔投票算法

摩尔投票算法最早由 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 = None
    count = 0

    for num in nums:
        if count == 0:
            candidate = num
        if candidate == num:
            count += 1
        else:
            count -= 1

    # 进行第二次遍历，验证 candidate 是否为多数元素
    count = 0
    for num in nums:
        if num == candidate:
            count += 1

    if count > len(nums) / 2:
        return candidate
    else:
        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)