题解 | #数组中出现次数超过一半的数字#

思路分析：消去法

• 在长度为9的数组[1,2,3,2,2,2,5,4,2]中，2的个数为5个，其余元素个数为4个;
• 将目标元素作为候选者，上述例子中，2为候选者，其余元素为非候选者。
• 候选者个数要比非候选者多，在遍历时，使用计数器count记录消去后候选者的个数；
• 消去法思路：遍历时，遇到候选者则count++，遇到非候选者则count--，当count为0时更新候选者。由于候选者个数大于非候选者个数，因此遍历结束后，count的个数大于0，其对应的候选者即为目标元素。

import java.util.*;
public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
        int target = -1;  // 记录候选者
        int count = 0;  // 候选者剩余个数
        for(int i = 0; i < array.length; ++i){
            if(count == 0){ // 选择新的候选者
                target = array[i];
                count++;
            } else {
                if(target == array[i]){
                    count++;  // 当前元素为候选者,对应的个数加1
                } else{
                    --count;  // 当前元素非候选者,候选者对应的个数减1
                }
            }
        }
        count = 0;
        // 确保正确，进一步判断
        for(int e : array){
            if(e == target){
                count++;
            }
        }
        if(count > array.length / 2){
            return target;
        }
        return -1;
    }
}