169. Majority Element

问题
Given an array nums of size n, return the majority element.

The majority element is the element that appears more than ⌊n / 2⌋ times. You may assume that the majority element always exists in the array.

Boyer-Moore投票算法
基本思想：
众数的值为+1，非众数的值为-1。其加和作为投票值。
遍历整个数组，由于众数数量大于非众数，因此最后结果一定为正数。

设置count记录票数，遍历数组。
当count为0时，则将当前的数组设为众数。当之后的数字与其相等，则count+1，反之则-1。
遍历完成后返回当前的众数。

• 根据以上规则，每次我们选择的众数，都是已遍历数组范围内出现最多次数的数值之一。

• 由于给定的数组的众数超过半数，因此遍历到最后的众数，一定是整个数组中出现最多次的数值。

核心就是对拼消耗。
玩一个诸侯争霸的游戏，假设你方人口超过总人口一半以上，并且能保证每个人口出去干仗都能一对一同归于尽。最后还有人活下来的国家就是胜利。

那就大混战呗，最差所有人都联合起来对付你（对应你每次选择作为计数器的数都是众数），或者其他国家也会相互攻击（会选择其他数作为计数器的数），但是只要你们不要内斗，最后肯定你赢。

最后能剩下的必定是自己人。

class Solution {
    public int majorityElement(int[] nums) {
        int count = 0;
        int major = 0;
        
        for(int num : nums){
            if(count == 0){
                major = num;
            }
            if(major == num){
                count++;
            }
            else{
                count--;
            }
        }
        return major;
    }
}

遍历数组，并将各个数值出现的次数记录在哈希表中。
当出现的次数大于数组的一半，则该数值是众数。

class Solution {
    public int majorityElement(int[] nums) {
        HashMap<Integer,Integer> map = new HashMap();
        for(int num : nums){
            map.put(num, map.getOrDefault(num,0)+1);
            if(map.get(num) > nums.length/2){
                return num;
            }
        }
        return -1;
    }
}