摩尔投票法+判断

    public int MoreThanHalfNum_Solution(int[] array) {
        // 摩尔投票法
        int cnt = 1;
        int num = array[0];
        for (int i = 1; i < array.length; i++) {
            if (num == array[i]) {
                cnt++;
            } else {
                cnt--;
                if (cnt == 0) {
                    if (i + 1 < array.length) num = array[i + 1];
                }
            }
        }
        //判断是否超过了一半
        cnt = 0;
        for (int i = 0; i < array.length; i++) {
            if (array[i] == num) cnt++;
        }
        return cnt <= array.length / 2 ? 0 : num;
    }