摩尔投票算法寻找多数元素

Question

我知道摩尔的投票算法找到多数元素有2个部分 -

1. 运行Moore投票算法的第一部分仅为您提供了一个候选人，在给定数组中大部分时间都会发生。注意这里的"最大"。
2. 在第二部分中，我们需要再次迭代数组，以确定该候选者是否发生最大次数（即大于大小/2次）。首先迭代是找到候选人＆amp;第二个迭代是检查此元素是否在给定数组中发生大部分时间。

因此，时间复杂性为：o（n） o（n）。

，但我只是想，而不是在数组上再次迭代，以查找它是否发生的数组大小/2次，我们不能做下面的事情？

我正在使用maxoCC跟踪当前最大元素。最后，如果MaxOCC> size/2，则我们的候选人是最大元素。这样，我们就不必按照算法的第二部分在整个数组中再次迭代。请让我知道这是否很好，还是我缺少什么？

void findMajorityElement()
{
    int arr[] = {10,8,8,8,8,8,8,10};
    int arrSize = 8;
    int mi = 0;
    int occ = 1;
    int maxOcc = 1;
    for(int i=1; i<arrSize-1; ++i)
    {
        if(arr[mi]==arr[i])
        {
            ++occ;
            ++maxOcc;
        }
        else
            --occ;
        if(occ == 0)
        {
            mi = i;
            occ = 1;
            maxOcc = 1;
        }
    }
    if(maxOcc > arrSize/2)
        cout <<"Majority element is "<<arr[mi]<<endl;
    else
        cout <<"Not Found!"<<endl;
}

此打印多数元素是8次，因为它发生了6次。因此，我们将另一个O（n）迭代保存在第二步所需的数组上。

请让我知道我是否缺少什么？

Answer 1

您对所谓的"摩尔的投票算法"的理解（我没有听说过这个名字，我以发明家的名字称呼它，我相信应该是称Moore-Boyer的投票算法）。正式地，该算法具有O(n+n) = O(2n) = O(n)时间复杂性。

但是，您对算法的修改未能在我链接到的网页上找到一个示例的多数元素，即： A A A C C B B C C C B C C：

int arr[] {1,1,1,3,3,2,2,3,3,3,2,3,3}; //A A A C C B B C C C B C C
int arrSize = 13;

这是因为算法是在O（n）中首先找到的点，然后在O（n）中检查它是否确实是多数元素。为了能够检查当前元素是多数元素，您必须增加时间复杂性。

另外，请注意，通过定义其定义的大多数元素，即使它们之间还有其他元素，您也可以计算等于多数元素的元素（例如： C C B B C C C）。

Answer 2

原始问题不假定候选人的所有投票都必须是连续的：如果是这样，您只能计算它们，直到投票更改，甚至可以宣布赢家在阅读整个数组之前。

如果候选人的投票不是连续的，但是您应该注意到

之后

AAABBBC

目前的"候选人"有1票，是" C"；这就是需要第二次通过的原因。

如果某人拥有绝对多数，那么它将显示为当前候选人（简单含义）。

您总是会在最后结束候选人，但是如果没有赢家，它可能只有一票。