描述：

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
例如：输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。
由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。

分析：

由于一个数字出现的次数超过数组长度的一半，则说明该数字一定是这个数组中出现次数最多的元素。那么这个题目可以转化为两个步骤：

1. 寻找数组中出现次数最多的元素；
2. 查看该元素在数组中的出现次数，若大于数组长度的一半，则返回该元素，反之则返回0

首先我们从简单的着手，统计数组中的一个元素出现的次数，十分简单，只需要循环一个该数组，便可得到结果。

接下来重点分析一下第一步，寻找数组中出现次数最多的元素，最简单的会想到利用一个辅助数组存储该数组每一个元素出现的次数，从其中寻找最大的即可，然而这种方法的空间复杂度会非常高，如果出现的元素的数值非常大的话，会造成辅助数组的空间大量被浪费。在这种情况下可以采用 Boyer-Moore Majority Vote Algorithm，这种算法可以达到时间复杂度为O(n)，空间复杂度为O(1)。

下面来介绍一下这个算法:
Boyer-Moore Majority Vote Algorithm（摩尔投票算法）：
该算法是基于这个事实：每次从序列里选择两个不相同的数字删除掉（或称为“抵消”），最后剩下一个数字或几个相同的数字，就是出现次数大于总数一半的那个。

在代码实现的时候，使用一个计数器count来统计一个元素出现的次数，当遍历到的元素和统计元素相等时，令 计数器加一，否则令计数器减一。如果前面查找了 i 个元素，且 count == 0，说明前 i 个元素没有 majority，或者有 majority，但是出现的次数少于 i / 2 ，因为如果多于 i / 2 的话 cnt 就一定不会为 0 。此时剩下的 n - i 个元素中，majority 的数目依然多于 (n - i) / 2，因此继续查找就能找出 majority。

代码实现：

 
public int MoreThanHalfNum_Solution(int [] array) {
        if (array.length==0||array==null)
        return 0;
        int majortiy=array[0];
        int count=1;
        //遍历数组找到出现次数最多的元素
        for (int i=1;i<array.length;i++){
            if (array[i]==majortiy)
                count++;
            else
                count--;
            //此时说明，数量最多的元素不存在或者不超过半数
            if (count==0){
                majortiy=array[i];
                count=1;
            }

        }
        //将计数器清零
        count=0;
        //再次遍历数组，统计出现最多元素的数量
        for (int e:array){
            if (e==majortiy){
                count++;
            }
        }
        if (count>array.length/2)
            return majortiy;
        else return 0;



    }

题目链接