seek_primary_element.cpp

两种确定某一数组是否有主元素的方法

// seek_primary_element.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include "iostream.h"
const int NUM=4;

int seek1(int a[],int low,int high)//采用分治算法，将问题平分为二
{
  int count1=0,count2=0,m,t1,t2;
  m=(low+high)/2;
  if(low==high)return a[low];
  else
  {
	  t1=seek1(a,low,m);
	  t2=seek1(a,m+1,high);
	  if(t1==t2)return t1;
	  else 
	  {
		  if(t1)
			  for(int i=0;i<high-low+1;i++)
				  if(a[i]==t1)count1++;
		  if(t2)
			  for(int i=0;i<high-low+1;i++)
				  if(a[i]==t2)count2++;
				  if(count1>(high-low+1)/2){count1=0;return t1;}
				  else if(count2>(high-low+1)/2){count2=0;return t2;}
		  else return 0;
		  
	  }
  }
}

int seek2(int a[],int n)
{
 int i,count=1,post=a[0];
 for(i=1;i<n;i++)
 {
	 if(post==a[i])count++;
	 else
	 {
		 if(count>0)count--;
		 else
		 {post=a[i];count++;}//count=0时，则post不可能是主元素，
		                     //重新选取侯选主元素
	 }
 }
 count=0;
 for(i=0;i<n;i++)
	 if(post==a[i])count++;
	 if(count>n/2)return post;
	 else return 0;
}


int main(int argc, char* argv[])
{
int n,a[NUM],t1,t2;
cout<<"Please input the Array:"<<endl;
for(int i=0;i<NUM;i++)cin>>a[i];

t1=seek1(a,0,NUM-1);
t2=seek2(a,NUM);
cout<<"第一种算法求主元素，结果为：\n";
if(t1)cout<<"The primary element is:"<<t1<<endl;
else cout<<"The primary element doesn't exist at all."<<endl;
cout<<"第二种算法求主元素，结果为：\n";
if(t2)cout<<"The primary element is:"<<t2<<endl;
else cout<<"The primary element doesn't exist at all.\n";
}