c++ - Boyer-Moore 多数投票算法的二次通过要求

Question

我正在研究 Boyer-Moore 算法(来自 here)，我有一个快速的问题 - 第二遍的需要是什么(它基本上只是通过找到该元素的频率来“确认”)。第一个传递本身不是保证找到的元素是多数元素吗？我考虑了几个示例，觉得单次通过就足够了。你能举一些例子来反驳我的感受吗？

代码(如果需要的话)如下:

int majorityElement(vector<int>& nums) {
    int candidate=0, count=0;

    for(auto value: nums) {
        //update the candidate if the count == 0
        if(count==0)
            candidate=value;

        //if the value == candidate then increment count
        if(value==candidate)
            count++;
        else
        //decrement count
            count--;
    }

    //return candidate
    return candidate;
}

编辑: 如果我理解正确，该算法仅适用于多数元素的频率确实大于 (vector size())/2 的情况。那么，真的需要第二遍吗？每当我们编码时，我们都会进行一些琐碎的健全性检查(比如检查输入 vector 是否为空)，所以在这种情况下，为什么我们要将“健全性检查”作为算法的一部分？或者还有其他原因？

Answer 1

我认为以下对 Boyer-Moore 算法的直觉可能会阐明为什么需要两次传递。

该算法基于以下思想。想象一下，数组中的每个元素都是房间里的一个人，手里拿着一张卡片，卡片上写着一个数字。房间里的每个人都四处游荡，直到遇到其他人。如果两个人拿着不同的数字，他们各自坐下。否则，他们会一直四处走动，直到遇到其他人。最终，一些人会留下来。

如果真的有多数派，那么最后站的那一组肯定是多数派，因为不管怎么配对，多数派的人太多了，不可能全部淘汰掉。但是，如果没有多数票，可能仍然会有人站在最后，持有非多数票。例如，也许他们只是碰巧在其他人都坐下时没有遇到具有不同值(value)观的人。

第二遍的原因是为了区分这两种情况。如果有多数票，它最终必须成为最终候选人。如果没有，某些东西可能仍会成为最终候选者，您需要排除这种情况。