求多数点的Moore投票算法

Question

我知道摩尔的投票算法有两个部分-

1. 运行摩尔投票算法的第一部分只给出了在给定数组中出现“大部分”时间的候选人。注意这里的“大多数”。
2. 在第二部分中，我们需要再次迭代数组，以确定该候选对象是否出现最大次数(即大于大小/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;
}

这个打印多数元素是8，因为它发生了6次。因此，我们在第二步所需的数组上保存了其他O(n)迭代。

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

Answer 1

你对你所谓的“摩尔投票算法”的理解(我还没听说过这个名字，我叫它发明家的名字，我认为它应该叫做摩尔-博耶投票算法)。在形式上，该算法具有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”，这就是为什么需要第二次通过。

如果某人拥有绝对多数票，那么它将在结尾处显示为当前候选人(简单含义)。

你最终总会有一个候选人，但如果没有胜利者的话，你可能只有一票。