public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
        int candidate = 0;//候选
        int count = 0;//次数
        for(int i = 0;i != array.length;i++){//核心代码：一次在数组中删掉两个不同的数字，不停的删除直到剩下的数只有一种，如果一个数字出现的次数大于一半，则这个数字一定会被剩下来，也就是最后的candidate值
            if(count == 0){
                candidate = array[i];
                count = 1;
            }else if(array[i] == candidate){
                count++;
            }else{
                count--;
            }
        }
        
        count = 0;
        for(int i = 0;i != array.length;i++){//如果是1，2，3，3会被剩下，这个for则检验剩下的数字出现的次数是否过半
            if(array[i] == candidate){
                count++;
            }
        }
        if(count > array.length / 2){
           return candidate;
        }else{
           return 0;
        }
     
    }
}