/*
*Author:        fdjiangwu
*Date:		2014.11.1
*Function:	大小为N的数组A，其主要元素是一个出现次数超过N/2次的元素，
*			如果数组中存在该元素，则找到该元素。
*Algorithm:	首先，找到主要元素的一个候选元(这是难点)。这个候选元是唯一有可能是主要元素的元素。
*			然后，确定该候选元是否就是主要元素。这正好是对数组的顺序搜索。
*			找到候选元的方法:为找到数组A的一个候选元，构造第二个数组B。
*			比较A1和A2，如果它们相等，则取其中之一到数组B中，否则什么都不做。
*			然后比较A3和A4，同样地，如果它们相等，则去其中之一到B中，否则什么都不做。
*			按照这种方式继续，直到读完这个数组。
*			然后递归地寻找数组B中的候选元，它也是A中的候选元。
*/
#include <stdio.h>
#define UNFOUND 0			
#define ONEFOUND 1

//将数组A和B都定义为全局变量，这样在递归的时候就不会每次都创建新的B数组。
int A[] = {3, 3, 4, 2, 4, 4, 2, 4, 3, 4, 4};
#define N (sizeof(A)/sizeof(A[0]))
int B[N/2 + 1];

//递归查找后院元的函数。
int findmainroleinarray(int A[], int n);

int main()
{
	int i;
	int count = 0;
	//maybemainrole标志是否找到候选元。
	int maybemainrole = UNFOUND;

	maybemainrole = findmainroleinarray(A, N);
	
	//如果存在候选元
	if(ONEFOUND == maybemainrole)
	{
		//B[0]存放候选元，搜索整个数组A
		for(i = 0; i < N; i++)
		{
			if(B[0] == A[i])
			{
				count++;
			}
		}
		
		if(count > N/2)
		{
			printf("Main role found: %d.\n", B[0]);
		}
		else
		{
			printf("Main role not found!\n");
		}
	}
	else
	{
		printf("Main role not found!\n");
	}

	return 0;
}

int findmainroleinarray(int A[], int n)
{
	int i;
	int k = 0;
	
	if(0 == n)
	{
		return UNFOUND;
	}
	else if(1 == n)
	{
		return ONEFOUND;
	}
	else 
	{
		for(i = 0; i < n; i = i + 2)
		{
			if(A[i] == A[i+1])
			{
				B[k] = A[i];
				k++;
			}
		}
		
		//对A数组是元素是基数的情况另作处理
		if((n % 2 == 1) && (A[n - 1] == A[n - 2]))
		{
			B[k] = A[n - 1];
			k++;
		}

		//递归调用
		return findmainroleinarray(B, k);
	}
}