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

import java.util.*;
public class Solution {
    /*数组中出现次数超过一半的数字
      1.哈希表
       -需要计算数组中元素出现的个数：使用hashMap
       -每次遍历遇到重复元素时判断value是否超过数组长度一半
      2.数组特性:某元素个数超过数组的一半,则必定存在相邻重复元素,必定在排序后中位数是该重复元素
         - a.排序后,直接取中位数
         - b.解法3
      3.士兵阵地战(留到最后的就是元素最多的那个 元素最多的A，对其他杂元素B)
        - 遍历数组,元素res 与上个士兵一致count++，否则count--
          - 若count==0,阵地被敌方占领,重置 res与count
          - 遍历完数组可以得到 士兵最多的那个元素
        - 最后判断该元素数量是否超过数组一半
    */
    public int MoreThanHalfNum_Solution(int [] array) {
        //阵地战
        int res = array[0];
        int count = 1;
        for(int i=1;i<array.length;i++){
            if(res==array[i]){
                count++;//友军
            }else{
                count--; 
                if(count==0){ //阵地被占领,换新的一方
                    res=array[i];
                    count=1;
                }
            }
        }
        //攻守结束,res即为最后剩下的count最多的一方
        //验证一下结果
        return res;
    }
}