【问题】

请编写下面函数 int MajorityElement(int array[],int n);

该函数返回数组array中的多数元素。多数元素是指在占绝对多数（至少51%）的一个值。假设多数元素不存在。那么返回常量NoMajorityElement,该函数必须满足以下的条件：

 1. 必须以O(N)时间执行。

 2. 必须使用O（1）的附加空间。换句话说，可用个别的暂时变量，而不能够使用不论什么的暂时数组。

而且不能使用递归解决，这是由于随着递归层数加深，会须要空间来存储栈帧。

3. 不能改变数组中的不论什么元素的值。

【代码】

#include <stdio.h>

void MajorityElement(int array[], int n)

{

	int majority, i, count;

	majority = array[0];

	count = 1;

	for(i = 1; i < n; i++){

		if(majority != array[i]){

			if(count == 0){

				majority = array[i];

				count++;

			}else{

				count--;

			}

		}else{

			count++;

		}

	}

	if(count > 0)

		printf("MajorityElement: %d\n", majority);

	else

		printf("NoMajorityElement\n");

}

main()

{

	int array[5] = {1, 2, 1, 2, 3};

	MajorityElement(array, 5);

}