169. 多数元素-Toy模板网

这篇具有很好参考价值的文章主要介绍了169. 多数元素。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

题目

169. 多数元素,# 简单题,力扣,python,开发语言

题解一：map集合计数

 /**
     * map集合计数
     * @param nums
     * @return
     */
    public static int majorityElement(int[] nums) {


        Map<Integer, Integer> map = new HashMap<>();

        //第一个for循环将数组中的元素作为key   出现次数作为value存入map  并且key重复  就value+1
        for (int i = 0; i < nums.length; i++) {

            if (map.containsKey(nums[i])) {
                map.put(nums[i], (map.get(nums[i]))+1);
            }else {
                map.put(nums[i],1);
            }
        }
        int maxKey = 0;   //记录最大value的key
        int maxValue =Integer.MIN_VALUE; //记住最大value

        //取出map集合最大的value
        for (Map.Entry<Integer,Integer> entry:map.entrySet()){
            int value = entry.getValue();
            if (value > maxValue) {
                maxValue = value;
                maxKey = entry.getKey();
            }
        }
        return maxKey;

    }

题解二：摩尔投票法思路

原理就是互相抵消，最后肯定是元素数量多的那个元素票数不为0
169. 多数元素,# 简单题,力扣,python,开发语言文章来源地址https://www.toymoban.com/news/detail-608459.html

/**
     *摩尔投票法思路
     * @param nums
     * @return
     */
    public static int majorityElement(int[] nums) {

        //默认候选人为第一个元素
        int candidate = nums[0];
        //默认切换候选人的票数为  1
        int count = 1;

        for (int i = 1; i < nums.length; i++) {

            //若元素相同  票数+1
            if (nums[i] == candidate) {
                count++;
            }else if(count > 0){//若元素不相同  票数-1
                count--;
            }

            if (count == 0){//若元素票数为0  换候选人  重置票数
                candidate = nums[i];
                count = 1;
            }

        }
        return candidate;

    }