摩尔投票法-数组中出现次数超过一半的数字

客官°小女子只卖身不卖艺 2022-12-08 04:15 164阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzgxMjYwOQ_size_16_color_FFFFFF_t_70_pic_center]

## 方法一 ##

##### 摩尔投票法 #####

用x记录当前众数，遍历数组，当前数字等于众数时vote加一，否则减一。当vote是0时更换众数。

public int majorityElement(int[] nums) { 
            int x = nums[0];
            int vote = 0;
            for(int k:nums){ 
                if(vote == 0) x = k;
                if(k == x){ 
                    vote++;
                }else{ 
                    vote--;
                }
            }
            return x;
            }
    }

## 方法二 ##

##### 哈希表存储遍历 #####

public int majorityElement(int[] nums) { 
            Map<Integer,Integer> map = new HashMap<>();
            for(int i:nums){ 
                if(map.containsKey(i)){ 
                    map.put(i,map.get(i)+1);
                }else{ 
                    map.put(i,1);
                }
            }
            int max = 0,result = 0;
            for(Integer key:map.keySet()){ 
                if(map.get(key)>max){ 
                    max = map.get(key);
                    result = key;
                }
            }
            return result;
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzgxMjYwOQ_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/174f78e6f7ba46e5b0e9641fc1718dee.png

发表评论取消回复

表情：

评论列表（有 0 条评论，164人围观）

还没有评论，来说两句吧...

相关阅读

相关 [剑指offer][JAVA]面试题第[39]题[数组中出现次数超过一半的数字][HashMap][摩尔投票法]

【问题描述】\[简单\] 数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。你可以假设数组是非空的，并且给定的数组总是存在多数元素

矫情吗；*/ 2023年02月20日 13:32/ 0 赞/ 96 阅读

相关摩尔投票法-数组中出现次数超过一半的数字

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ub

客官°小女子只卖身不卖艺/ 2022年12月08日 04:15/ 0 赞/ 165 阅读

相关数组中出现次数超过一半的数字

题目：数组中有一个数字出现的次数超过了数组长度的一半，找出这个数字。 1.使用排序算法，将整个数组排序，然后中间的数字就是出现次数超过一半的数字。时间复杂度为O(nlogn)

- 日理万妓/ 2022年08月06日 00:12/ 0 赞/ 193 阅读

相关数组中出现次数超过一半的数字

剑指offer面试题29~数组中出现次数超过一半的数字一.问题描述数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组\{1,2

绝地灬酷狼/ 2022年06月17日 06:43/ 0 赞/ 212 阅读

相关数组中出现次数超过一半的数字

链接： [https://www.nowcoder.com/questionTerminal/e8a1b01a2df14cb2b228b30ee6a92163][https_w

逃离我推掉我的手/ 2022年06月07日 02:25/ 0 赞/ 232 阅读

相关找出数组中出现次数超过一半的数+ 寻找众数 + 摩尔投票法

排序就是先做排序，然后找中位数 map统计直接使用map统计出现次数，然后遍历map即可缩小范围每次取出两个不同的数，剩下的数字中重复出现的数字肯

r囧r小猫/ 2022年05月30日 02:39/ 0 赞/ 238 阅读

相关数组中出现次数超过一半的数字

[数组中出现次数超过一半的数字][Link 1] 题目描述数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组\{1,2,3,

ゝ一世哀愁。/ 2022年03月25日 15:29/ 0 赞/ 218 阅读

相关数组中出现次数超过一半的数字

何海涛：《剑指Offer：名企面试官精讲典型编程题》：九度OJ 题目描述：[http://ac.jobdu.com/problem.php?cid=1039&pid=12][

ゝ一纸荒年。/ 2022年03月20日 02:50/ 0 赞/ 223 阅读

相关【剑指Offer】（数组）数组中出现次数超过一半的数字（摩尔投票法）

题目链接：[https://www.nowcoder.com/practice/e8a1b01a2df14cb2b228b30ee6a92163?tpId=13&tqId=11

约定不等于承诺〃/ 2022年03月16日 12:48/ 0 赞/ 165 阅读

相关数组中出现次数超过一半的数字

时间限制：1秒空间限制：32768K 热度指数：281239 本题知识点：数组算法知识视频讲解题目描述数组中有一个数字出现的次数超过数组长度的一半，请

小咪咪/ 2022年03月09日 10:46/ 0 赞/ 240 阅读