学步园

如果不优化时间复杂度的话，可以先对整个数组进行排序，最好的时间复杂度是O(nlgn)，然后数组的中间那个数就是次数超过一半的数。如果不优化空间复杂度的话，可以利用哈希表将出现的数保存起来，key为该数，value为该数出现的次数。关键在于如何设计哈希函数，可以借助stl中的map容器实现，空间复杂度是O(n)。

     以上的方法都不是最优的，可以从另外一个方面考虑。假设某个数出现的次数大于数组的一半，则这个数出现的次数大于其他任何数出现的次数。因此可以将数组的左右数比较，如果相等，则前一个数的计数增一，如果不相等，则前一个数的计数减一，如果计数值为0，则将Pos设为右边的数。这样直到数组末尾，pos就是数组超过一半的数了。

    假设某个数出现的次数刚好等于数组的一半，对于2 2 2 1 3 4，上述的方法就会将4作为最终值。需要修改上述逻辑，可以这样考虑，如果最后一个数刚好不是我们所要找的数，则把他去除，前面有2n-1个数，这里面的数2出现n次，超过2n-1的一半，用上述的方法可以找出。那么，问题就转换成，怎样才能判定最后一个数不是我们需要找的呢？可以再设一个变量equal，从数组开始遍历，如果a[i]==a[2n]，则equal++，达到结尾时，判断equal的值是否达到数组一半，如果没有，则肯定不是。代码如下：

#include <iostream>
using namespace std;
int moreThanHalf(int A[], int n) {
	int i, pos=A[0], co=1, equal=0;
	if (n==1) {
		return pos;
	}
	equal = equal + (A[0]==A[n-1]?1:0);
	for (i=1; i<n; ++i) {
		if (A[i] == A[n-1]) {
			equal++;
		}
		if (A[i] == A[i-1]) {
			co++;
		}
		else {
			co--;
			if (co == 0) {
				if (i==n-1 && !(n&1) && equal<n/2) {
					continue;
				}
				co = 1;
				pos = A[i];
			}
		}
	}
	return pos;
}
int main() {
	int n;
	cin >> n;
	int *f = new int[n];
	int i;
	for (i=0; i<n; ++i) {
		cin >> f[i];
	}
	cout << moreThanHalf(f, n) << endl;
	delete []f;
	return 0;
}