p99 寻找多数元素

大家好，欢迎来到IT知识分享网。

寻找多数元素

// 寻找多数元素.cpp : Defines the entry point for the console application.
//

#include “stdafx.h”
#include<iostream>
using namespace std;

int candidate(int m,int n,int A[])
{

 int j=m, c=A[m],count=1;
 while(j<n && count>0)
 {

  j=j+1;
  if(A[j]==c) count=count+1;
  else count=count-1;
 }
 if(j==n) return c;
 else return candidate(j+1,n,A);
 return 0;

}

int main(int argc, char* argv[])
{

 int n,c,count=0,A[10];
 cout<<“请输入元素的个数”<<endl;
 cin>>n;
 cout<<“请输入”<<n<<“个元素”<<endl;
 for(int i=1;i<=n;i++) cin>>A[i];
 c=candidate(1,n,A);
 for(int j=1;j<=n;j++)
 {

  if(A[j]==c)
  {

   count=count+1;
  }
 }
 if(count>int(n/2)) cout<<c<<“是多数”<<endl;
 else cout<<“该序列没有多数”<<endl;

 return 0;
}