效率最高的解法

看到好多人用排序或者哈希表。其实没必要这么复杂，我们想，一个数组中有一个数字出现的次数，超过一半，那arr[half]必定是这个数字，其中half=arr.length/2。那这样就简单了，遍历一遍数组，统计arr[half]出现的次数，看是否超过数组长度的一半即可。代码如下：

public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
        if (array==null||array.length==0)
            return 0;
        int half=array.length/2;
        int num=array[half];
        int count=0;
        for (int item:array){
            if (item==num)
                ++count;
        }
        if (count>half)
            return num;
        return 0;
    }
}

效率应该比排序或哈希表的时间和空间效率都要好得多。