编写一个函数Int MajorityElement(int array[],int n);
该函数返回数组array中的多数元素。多数元素是指在占绝对多数（至少51%）的一个值。如果多数元素不存在，那么返回常量NoMajorityElement,该函数必须满足下面的条件：
1. 必须以O(N)时间运行。
2. 必须使用O（1）的附加空间。换句话说，可用个别的临时变量，而不可以使用任何的临时数组。并且不能使用递归解决，这是因为随着递归层数加深，会需要空间来存储栈帧。
3. 不能改变数组中的任何元素的值。

要是可以给一个临时数组，这个问题就好办了，关键是只能用到O（1）的附加空间。
大家看能不能给点思路

n代表数组array的元素个数

楼上有能在线性时间内完成数组排序的算法吗？

楼上的不知道有没有什么好方法