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

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

好像要求很苛刻的样子，问一下，参数n干嘛用的？一起想下呵

我晕，你返一个int型，也就定义一变量，然后返回，而这个变量什么占多数元素呀，不懂。没看明白，自己好逐磨吧

楼主的意思是在数组中出现最频繁的那个值呵

n代表数组array的元素个数

遍历数组,把出现次数大于n/2的那个输出,再一次遍历数组,但这时不用访问跟之前相等的数...

楼上的方法就不是线性时间给出结果了。

我有一个赖皮的方法，楼主要求用O（1）的空间，我是不是可以理解为一个字符串的空间？这样的话我就可以编一个字符串，通过字符串编码获得各元素出现次数的信息了。

我想先把数组排序，字符一样的在一起。然后在一个用二个变量，比较；直到选择最大的

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

这个O（1）太恶心了