题解 | #数组中出现次数超过一半的数字#一次遍历找出目标数字

题目描述
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。
示例1
输入
复制
[1,2,3,2,2,2,5,4,2]
返回值
复制
2

多数解决方案选择两次遍历找出目标，在摩尔投票法的基础上，本解给出借助辅助变量tag一次遍历找出目标的方法

public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
        //摩尔投票法，cond用来记录候选人
        int cond = -1;
        //cnt记录票数
        int cnt = 0;
        //辅助变量tag用来记录上一个cond，默认值为-1
        int tag = -1;
        for (int i = 0; i < array.length; ++i){
        //每次候选人选票为零时，更换为下一个候选人
            if (cnt == 0){
        //tag记录上一个候选人，如果第一个数字选为候选人之后未曾更换，tag==-1
                tag = cond;
                cond = array[i];
                ++cnt;

            }
            else {
                if (cond == array[i]) ++cnt;
                else {
                --cnt;}

            }
        }

        //cnt > 0 && tag == cond 识别数组长度为奇数且最后一位数字是目标数字的情况
        //tag == -1 识别候选人未曾变更过的情况
        //cnt > 1识别目标数字出现次数大于**总数一半+1**的情况
        if ( (cnt > 0 && tag ==cond) || tag == -1 || cnt > 1){
            return cond;
        }
        return 0;
    }
}