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

Question

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

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

所以时间复杂度是:O(n) + O(n)。

但我只是想与其再次遍历数组以查找它是否出现超过 Array Size/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)。