时间多数投票算法错误

Question

这是算法http://www.cs.utexas.edu/~moore/best-ideas/mjrty/example.html，这是我的代码

#include <iostream>
using namespace std;
int main(){
    int n;
    cin>>n;
    int ans,counter=0,a,temp=0,time=0;
    while(temp<n){
        cin>>a;
        if(counter==0)
        {
            counter=1;
            ans=a;
        }
        else if(counter>0){
            if(ans==a)
                ++counter;
            else
                --counter;
        }
        ++temp;
    }
    cout<<"The number "<<ans<<" is in the more majority ";
}

我的问题是，当你给出6，6，1，2，3的时候，它说3占多数

我的问题在哪里？谢谢

Answer 1

您正确地实现了算法，但是您没有正确地解释它。

该算法假设存在多数元素(超过一半的元素是该特定元素)，并返回该元素。如果假设为假，您必须检查整个序列两次，以检查是否真的存在多数。

在您的示例中没有多数，因此算法不起作用。

Answer 2

我认为对于给定的数据，您已经得到了预期的答案。关键是链接页面中的这句话：

“当我们完成时，如果存在多数，则当前候选人是多数元素。”

在这种情况下，没有多数，因此算法返回无效结果。使用输入6 6 6 1 2重试

这是一个没有数组的实现，教授不太可能接受：

#include <iostream>
using namespace std;
int majority(int n,int &ans,int counter){
  int a,i;
  if (!n) return 0;
  cin>>a;
  if (!counter) ans=a;
  counter+=2*(ans==a)-1;
  i=majority(n-1,ans,counter);
  return i+(ans==a);
}
int main(){
  int n,ans;
    cin>>n;
     if (n/2 < majority(n,ans,0))
        cout<<"The number "<<ans<<" is in the more majority "<<endl;
     else 
        cout<<"No majority"<<endl;
}