3

我正在研究 Boyer-Moore 算法（从这里开始），我有一个快速的问题 - 第二遍需要什么（基本上只是通过找到该元素的频率来“确认”）。第一遍本身不能保证找到的元素是大多数元素吗？我考虑了几个例子，觉得一次通过就足够了。您能否提供一些例子来反驳我的感受？

代码（如果需要）如下：

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. 那么，真的需要第二遍吗？每当我们编写代码时，我们都会进行一些琐碎的完整性检查（例如检查输入向量是否为空），那么在这种情况下，为什么我们将“完整性检查”作为算法的一部分呢？或者还有更多的东西吗？

4

2 回答 2

2

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

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

如果有真正的多数派，最后站的那群人肯定是多数派，因为无论人们怎么配对，多数派的人太多了，以至于他们都被淘汰了。但如果没有多数，仍然可能有人站在最后，持有非多数。例如，也许他们只是碰巧没有遇到价值不同的人，而其他人都坐了下来。

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

于 2017-11-04T04:06:33.833 回答
0

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

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

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

例如：- 在以下列表中

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

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

我希望它有帮助！

于 2017-10-07T00:16:51.980 回答