c++ - 寻找多数元素的摩尔投票算法

Question

据我所知，寻找多数元素的摩尔投票算法有两部分 -

1. 运行摩尔投票算法的第一部分仅给出给定数组中“大多数”时间出现的候选者。注意这里的“最”。
2. 在第二部分中，我们需要再次迭代数组以确定该候选是否出现最大次数(即大于 size/2 次)。 第一次迭代是找到候选元素，第二次迭代是检查该元素是否在给定数组中出现大多数次数。

所以时间复杂度为: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;
}

这会打印出 Majority element is 8，因为它出现了 6 次。 因此，我们保存第二步所需的数组上的其他 O(n) 迭代。

如果我遗漏了什么，请告诉我？

Answer 1

你对所谓“摩尔投票算法”的理解(我没听说过这个名字，我用发明者的名字来调用它，我相信它应该被称为 Moore-Boyer's voting algorithm )。形式上，该算法的时间复杂度为 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)。