【leetcode刷题】11.多数元素——Java版

前言

哈喽，大家好，我是一条

糊涂算法，难得糊涂

昨天面试字节，切实感受到了刷算法带来的提升

生命不息，刷题不止

Question

169. 多数元素

难度：简单

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

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

示例 1：

输入：[3,2,3]
输出：3

示例2:

输入：[2,2,1,1,1,2,2]
输出：2

进阶：

尝试设计时间复杂度为 O(n)、空间复杂度为 O(1) 的算法解决此问题。

Solution

一条开始采用的hashmap计数法，不用想，结果肯定超时了

足足17ms

HashMap<Integer, Integer> map = new HashMap<>();
       for (int i = 0; i < nums.length; i++) {
           if (map.containsKey(nums[i])){
               map.put(nums[i],map.get(nums[i])+1);
               if (map.get(nums[i])>nums.length/2){
                   return nums[i];
               }
           }else {
               map.put(nums[i],1);
           }
       }
       return nums[0];

后来发现有个方法叫摩尔投票

摩尔投票法

核心就是对拼消耗。

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

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

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

定义一个计数器count=1，多数元素cur=numsp[0]

如果当前数字和多数元素相同，count++

如果当前数字和多数元素不同,count--

如果count==0，更换cur的值

理解了摩尔投票法后，良心推荐一道进阶的题目：求众数Ⅱ

Code

所有leetcode代码已同步至github

欢迎star

class Solution {
    public int majorityElement(int[] nums) {
        int cand_num = nums[0], count = 1;
        for (int i = 1; i < nums.length; ++i) {
            if (cand_num == nums[i]) {
                ++count;
            }else if (--count == 0) {
                cand_num = nums[i];
                count = 1;
            }
        }
        return cand_num;
    }
}

Result

复杂度分析

• 时间复杂度：O(N)

🌈寻宝

⭐今天是坚持刷题更文的第11/100天

⭐各位的点赞、关注、收藏、评论、订阅就是一条创作的最大动力

⭐更多算法题欢迎关注专栏《leetcode》

为了回馈各位粉丝，礼尚往来，给大家准备了一条多年积累下来的优质资源，包括 学习视频、面试资料、珍藏电子书等

怎么领取请大家自己找，寻宝游戏现在开始。

找不到可以评论留言，一条就会注意到你。

如果还不行，请私信我。