42

当我阅读本文时（在数组中查找最常见的条目），建议使用Boyer 和 Moore 的线性时间投票算法。

如果您点击该网站的链接，则会逐步解释该算法的工作原理。对于给定的序列，AAACCBBCCCBCC它提供了正确的解决方案。

当我们将指针向前移动到元素 e 上时：

  • 如果计数器为 0，我们将当前候选设置为 e，并将计数器设置为 1。
  • 如果计数器不为 0，我们根据 e 是否是当前候选者来增加或减少计数器。

完成后，如果有多数，则当前候选人是多数元素。

如果我在一张纸上使用这个算法AAACCBB作为输入，建议的候选人将变成 B，这显然是错误的。

在我看来，有两种可能

  1. 作者从未在任何其他方面尝试过他们的算法AAACCBBCCCBCC，完全无能，应该当场解雇（怀疑）。
  2. 我显然遗漏了一些东西，必须从 Stackoverflow 被禁止，并且永远不能再接触任何涉及逻辑的东西。

注意：这是来自 Niek Sanders的算法的 C++ 实现。我相信他正确地实现了这个想法，因此它有同样的问题（或者不是吗？）。

4

5 回答 5

45

该算法仅在集合具有多数时才有效 - 超过一半的元素相同。AAACCBB在你的例子中没有这样的多数。最常见的字母出现 3 次，字符串长度为 7。

于 2009-04-23T09:28:40.713 回答
28

对其他解释的小而重要的补充。摩尔的投票算法有 2 个部分 -

  1. 运行摩尔投票算法的第一部分只为您提供多数元素的候选人。请注意这里的“候选人”一词。

  2. 在第二部分中，我们需要再次遍历数组以确定该候选是否出现最大次数（即大于 size/2 次）。

第一次迭代是找到候选者，第二次迭代是检查这个元素是否在给定数组中出现大多数次。

所以时间复杂度为：O(n) + O(n) ≈ O(n)

于 2013-07-03T13:16:09.200 回答
7

从第一个链接的 SO 问题开始：

具有数组中超过一半的条目等于 N 的属性

来自 Boyer 和 Moore 页面：

序列的哪个元素占多数，前提是存在这样的元素

这两种算法都明确假设一个元素至少出现 N/2 次。（特别注意“多数”与“最常见”不同。）

于 2009-04-23T09:31:05.123 回答
0

我为这个算法写了一个 C++ 代码

char find_more_than_half_shown_number(char* arr, int len){
int i=0;
std::vector<int> vec;
while(i<len){
    if(vec.empty()){     
        vec.push_back(arr[i]);
        vec.push_back(1);
    }else if(vec[0]==arr[i]){ 
        vec[1]++;
    }else if(vec[0]!=arr[i]&&vec[1]!=0){
        vec[1]--;
    }else{                   
        vec[0]=arr[i];
    }
    i++;
}
int tmp_count=0;
for(int i=0;i<len;i++){
    if(arr[i]==vec[0])
        tmp_count++;
}
if(tmp_count>=(len+1)/2)
    return vec[0];
else
    return -1;
}

主要功能如下：

int main(int argc, const char * argv[])
{
    char arr[]={'A','A','A','C','C','B','B','C','C','C','B','C','C'};
    int len=sizeof(arr)/sizeof(char);
    char rest_num=find_more_than_half_shown_number(arr,len);
    std::cout << "rest_num="<<rest_num<<std::endl;
    return 0;
}
于 2014-01-29T19:35:55.533 回答
0

当测试用例为“AAACCBB”时，集合没有多数。因为“AAACCBB”的长度是 7，所以没有元素出现超过 3 次。

这是“博耶和摩尔的线性时间投票算法”的代码：

int Voting(vector<int> &num) {
        int count = 0;
        int candidate;

        for(int i = 0; i < num.size(); ++i) {
            if(count == 0) {
                candidate = num[i];
                count = 1;
            }
            else
                count = (candidate == num[i]) ? ++count : --count;
        }
        return candidate;
    }
于 2014-12-23T16:33:09.483 回答