哈希法

• 用map存储每个键值的出现次数，存完检查为众数直接返回该数，循环结束直接返回0

  import java.util.*;
  public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
        Map<Integer,Integer> map = new HashMap();
       for(int e : array) {
           // 记录e出现次数
           if(map.containsKey(e)) {
               map.put(e,map.get(e) + 1);
           } else {
               map.put(e, 1);
           }
  
           // 超过一半则直接返回
           if(map.get(e) > array.length / 2) {
               return e;
           }
       };
       return 0;
    }
  }

候选人法

• 若一定存在一个众数：遍历数组，每到一个元素会经历一次投票，如果目前候选人为自己，票+1，否则票-1，由于众数出现次数超过其他所有数，所以即使其他人全投的众数反对票，众数也能当任，即最后剩下的候选人为众数
• 若不一定存在众数：候选人法可能出现问题，则再遍历一边查看是否为众数即可

import java.util.*;
public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
        int people = 0, tickets = 0;
        // 轮流投票
        for(int e : array) {
            // 新人上任
            if(tickets == 0) {
                people = e;
            }

            // 支持自己，反对别人
            if(people == e) {
                tickets++;
            } else {
                tickets--;
            }
        }

        // 检测该数是否为众数
        tickets = 0;
        for(int e : array) {
            if(e == people && ++tickets > array.length / 2) {
                 return people;
            }
        }
        return 0;
    }
}