思路分析:消去法

  • 在长度为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;
    }
}