最简单的算法 摩尔投票

假设当前序列总有数字出现的个数超过了一半！
那么，每次任选两个不同的数字，并把他们都删除，则最后剩下的数字（一个或多个），一定为众数
因为众数出现的数字超过了一半，所以我们可以把数字任意拆分成两个数目相等的集合，每次从集合 a 和 集合 b 中各取一个数，如果他们俩不相同，就都扔掉，根据鸽巢原理，总有一次，你会从两个集合中，取出相等的数。
搬运自Krahets leetcode大佬发的题解

public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
        int votes = 0,x = 0;
        for(int i : array) {
            if(votes == 0) x = i;
            votes += (i == x ? 1 : -1);
        }
        int num = 0;
        for(int i : array) {
            if(i == x) num ++;
        }
        if(num > array.length / 2) return x;
        else return 0;
    }
}