多数元素：擂台相消

题目

给定一个大小为 n的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

思考

看到这道题我们先想想暴力法怎么解决，无非是map推一个找数，易得代码

import java.util.HashMap;
import java.util.Map;

class Solution {
    public int majorityElement(int[] nums) {
//        创建一个哈希表用来存储出现频率
        Map<Integer,Integer> map = new HashMap<>();
//        目标值
        int target = nums.length / 2;
//        开始找数频率
        for (int num : nums) {
            map.put (num, map.getOrDefault(num, 0) + 1);
            if (map.get(num) > target) {
                return num;
            }
        }
//        避免报错
        return -1;
    }
}

暴力法出现了挺多问题的，有些数其实没必要处理却被我们处理掉了，而且开了哈希额外空间，我们反过来想想，多数元素超过一半了，如果我们让每个元素pk，最后剩下的是不是多数元素，因为他多于一半，其他的一起上也干不死他，这就是摩尔投票法，看代码

class Solution {
    public int majorityElement(int[] nums) {
//        候选人
        int can = 0;
//        票数
        int count = 0;
        for (int i = 0; i < nums.length; i++) {
//            零票出局
            if (count == 0) {
                can = nums[i];
            }

//            候选人系统加票，否pk同归于尽
            if (can == nums[i]) {
                count ++;
            } else {
                count --;
            }
        }
        return can;
    }
}

‍