线性时间投票算法。 我不明白

Question

当我阅读本文时（查找数组中最常见的条目），博耶和摩尔的线性时间建议采用投票算法。

如果您点击该网站的链接，就会看到该算法如何工作的分步说明。 对于给定的序列，AAACCBBCCCBCC 它提供了正确的解决方案。

当我们将指针向前移动时 元素 e:

• 如果计数器为 0，我们将当前候选设置为 e，并将 与 1 相反。
• 如果计数器不为 0，我们将递增或递减计数器 根据e是否是当前的 候选人。

当我们完成后，当前 候选者是多数元素，如果 有大多数。

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

在我看来，有两种可能性。

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

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

Answer 1

该算法仅在集合占多数时才起作用——超过一半的元素相同。 在您的示例中，AAACCBB 没有这样的多数。 最常见的字母出现了 3 次，字符串长度为 7。

Answer 2

虽然很小，但对其他解释来说是一个重要的补充。 摩尔投票算法有 2 个部分 -

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

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

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

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

Answer 3

从第一个链接的SO问题：

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

来自 Boyer 和 Moore 页面：

如果存在这样的元素，则序列中哪个元素占多数

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

Answer 4

我为这个算法写了一个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;
}

Answer 5

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

以下是“Boyer 和 Moore 的线性时间投票算法”的代码：

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;
    }