[数据结构与算法]数组找主元素

• 已知一个整数序列A = ( a0，a1，…an-1),其中0≤ai＜n（0≤i＜n）。若存在ap1=ap2=···=apm=x，且m>n/2（0＜pk＜n，1≤k≤m），则称x为A的主元素。例如A=（0,5,5,3,5,7,5,5），则5为主元素；又如A = ( 0,5,5,3,5,1,5 ,7 )，则A中没有主元素。 假设A中的几个元素保存在一个一维数组中，请设计一个尽可能高效的算法，找出A的主元素。若存在主元素，则输出该元素；否则输出-1。要求：

(1) 给出算法的基本设计思想

(2) 根据设计思想，釆用C或C++或Java语言描述算法，关键之处给出注释。

(3) 说明你所设计算法的时间复杂度和空间复杂度。

int findMain(int A[], int n) {
	int count[n] = {0};
	
	for (int i = 0; i < n; i++) {
		count[A[i]]++;		//记录数字出现的次数
	}
	
	for (int i = 0; i < n; i++) {
		if (count[i] > (n / 2))
			return i;		//严格大于数字个数的一半，便是该数字
		
		else
			return -1;		//-1 表示A数组中没有主元素
	}
}