【每日leetcode】9.多数元素

一条coding

发布于 2021-08-12 10:31:04

3230

发布于 2021-08-12 10:31:04

文章被收录于专栏：一条IT

从第一个数开始count=1，遇到相同的就加1，遇到不同的就减1，减到0就重新换个数开始计数，总能找到最多的那个 ——leetcode此题热评

前言

哈喽，大家好，我是一条糊涂算法，难得糊涂昨天面试字节，切实感受到了刷算法带来的提升生命不息，刷题不止

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 https://github.com/lbsys/leetcode/tree/master/src/leetcode/editor/cn 欢迎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;
    }
}