关于主元素的线性算法和递归算法

分析：
算法采用快速排序的思想，根据相等与不等进行两边划分，相等部分的计数器如果不大于n/2，则对不等部分递归求解。
实现：
#include "iostream.h"
#include "stdlib.h"
#include "time.h"
#define N 10

int master( int temp[], int start, int end );
void insert( int temp[], int inspos, int end, int ins );

void main()
{
 //Test data:
 cout << "Test:n = " << N << endl << endl;
 cout << "The random Array below:" << endl;
 srand( (unsigned)time( NULL ) );
 int* temp = new int[N];
 for( int i = 0; i < N; i++ )
 {
  temp[i] = (int)(((float)rand()/65535*4)+1);
  cout << temp[i] << " ";
 }
 cout << endl << endl;
 int masterNum = master( temp, 0, N );
 if( masterNum == 0 )
 {
  cout << "There is no master number in the Array!" << endl;
 }
 else
 {
  cout << "There is a master_number in the Array!"<< endl;
 }
}

int master( int temp[], int start, int end )
//函数的作用是递归方法求解是否有主元素，如果没有返回0，有的话返回主元素在集合中的个数；
{
 if( start >= N / 2 )
 {
  return 0;
 }
 int k = 1;
 int tempInt = temp[start];
 for( int i = start + 1; i < end; i++ )
 {
  if( tempInt == temp[i] )
  {
   insert( temp, start + k, i, tempInt );
   k++;
  }
 }
 if( k > N / 2 )
 {
  return k;
 }
 else
 {
  return master( temp, start + k, end );
 }
}

void insert( int temp[], int inspos, int end, int ins )
//数据移位运算，作为原运算；
{
 for( int i = end; i > inspos; i-- )
 { 
  temp[i] = temp[i-1];
 }
 temp[inspos] = ins;
}

算法时间复杂度分析：
由于本算法采用了与快速排序相同的方法，所以其时间复杂度与快速排序相同
O（nlogn）；
改进算法：
算法依据在一个集合中，删除两个不同的数，则集合的主元素保持不变，故我们可以  通过此原理来实现线性时间算法，算法复杂度为O（n）；
改进算法实现：
bool master( int temp[] )
{
 int count = 1;
 int seed = temp[0];
 for( int i = 1; i < N; i++ )
 {
  if( temp[i] == seed )
  {
   count++;
  }
  else
  {
   if( count > 0 )
   {
    count--;
   }
   else
   {
    seed = temp[i];
   }
  }
 }
 count = 0;
 for( i = 0; i < N; i++ )
 {
  if( temp[i] == seed )
  {
   count++;
  }
 }
 if( count > N/2 )
 {
  return true;
 }
 else
 {
  return false;
 }
}

本文地址：http://com.8s8s.com/it/it32116.htm