要求O(n)时间复杂度。

利用“已经知道这个数字在整个数组中出现的比例超过50%”这个事实，采用计数法。

设置两个变量：number表示在遍历过程中出现次数最多的数，flag表示在遍历过程中该数字出现的次数与其他数字出现次数之差。初始化flag为0。

从头遍历数组，首先判断flag是不是为0，如果为0，则number记为当前遍历的数，并且flag++，继续向下遍历（此处需要说明的是，flag为0表示现在尚没有找到某个数次数比别人都多的）

若flag不等于0，那么说明前边有一个数number可能是最后答案，此时将该number与遍历位置上的数字进行比较，相等flag++，不等flag—。

这样遍历完最后得到的number即为所求，此时flag表示出现超过一半的这个数比其余数字多的次数，利用这个数字也可以得到这个出现次数超过一半的数究竟出现了几次，即(SIZE+flag)/2。

实现如下：

 

本文转自gnuhpc博客园博客，原文链接：http://www.cnblogs.com/gnuhpc/archive/2012/12/21/2828073.html，如需转载请自行联系原作者