解法一：统计次数法

HashMap即可 略

解法二：候选法

（抱对自杀，双双殉情）
由于我们不知道数组中是否一定存在这样的数，所以后面还是需要验证这个数是否过半了。

public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
        if(array==null||array.length==0) return 0;
        int ans=array[0];
        int count=1;
        for(int i=1; i<array.length; i++){
            if(count==0) ans=array[i];
            if(array[i]==ans) count++;
            else count--;
        }
        count=0;
        for(int i=0; i<array.length; i++){
            if(array[i]==ans) count++;
        }        
        return count>array.length/2? ans:0;
    }
}

解法三：排序选中位数法

非原创， 感谢：
https://blog.nowcoder.net/n/a096f9b217b04c90bc4b7d968ff0c409?f=comment
原理：如果一个数的出现频率占据了一半以上，经过排序之后，同一个数字分布是连续的。那么取中间的那个数字，一定是这个众数。
和上面相同，由于我们不知道数组中是否一定存在这样的数，所以后面还是需要验证这个数是否过半了。
最后一行代码就是干这件事情的。

IntStream.of(array).filter(k->k==i).count()>array.length/2?i:0;

稍微解释一下

• IntStream.of(array)，把数组array中的元素按顺序放在流中
• IntStream.of(array).filter(k->k==i)，经过过滤器返回的类型依然是IntStream，此时流中每一个元素都是i本身。
• IntStream.of(array).filter(k->k==i).count()，返回该流中的元素个数。即array中和i相等的元素个数。
• IntStream.of(array).filter(k->k==i).count()>array.length/2?i:0; 如果i的出现频率过半就返回i，否则返回0.

(很神奇的一点，牛客的在线编辑器找不到找不到IntStream，而Java8的API 明明白白写着它在这里
java.util.stream
https://docs.oracle.com/javase/8/docs/api/java/util/stream/IntStream.html

完整代码在这里

public int MoreThanHalfNum_Solution(int [] array) {
    Arrays.sort(array);
    int i=array[array.length/2];
    return IntStream.of(array).filter(k->k==i).count()>array.length/2?i:0;
}