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

Question

我正在研究 Boyer-Moore 算法（来自 here），我有一个快速的问题 - 第二遍的需要是什么（本质上只是 'confirms' 通过找到频率那个元素）。难道第一个通过本身保证找到的元素是多数元素吗？我考虑了几个例子，觉得单次通过就足够了。能否请您提供一些例子来反驳我的感受？

代码（如果需要）如下：

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的情况。那么，真的需要第二遍吗？每当我们编码时，我们都会进行一些琐碎的健全性检查（比如检查输入向量是否为空），所以在这种情况下，为什么我们将 'sanity check' 作为算法的一部分？或者还有更多内容？

Answer 1

我猜你对什么是多数元素感到困惑。候选人只有在其频率超过总列表的一半时才有资格，即

if frequency(majority_element) > total_size_of_list / 2: return True

第一次通过只获得多数投票的可能候选人。第二遍确认它是否真的是多数元素。

例如：- 在以下列表中

[1, 2, 2, 3, 3, 4, 4, 5, 5, 5]

多数元素的可能候选者是 5。但是列表中 5 的频率仅为 3，小于列表大小的一半，因此它不是多数元素，因此测试失败，但如果你不进行第二遍，你甚至不会知道它。

希望对您有所帮助！

Answer 2

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

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

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

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

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

Requirement of second pass for the Boyer-Moore Majority Vote Algorithm

c++

algorithm

boyer-moore