侧边栏壁纸
博主头像
阿里灰太狼博主等级

You have to believe in yourself . That's the secret of success.

  • 累计撰写 104 篇文章
  • 累计创建 50 个标签
  • 累计收到 12 条评论

目 录CONTENT

文章目录

leetcode-169. 多数元素

阿里灰太狼
2021-11-21 / 0 评论 / 0 点赞 / 141 阅读 / 693 字 / 正在检测是否收录...
温馨提示:
本文最后更新于 2021-11-21,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

cj60.png

JAVA解法

class Solution {
    public int majorityElement(int[] nums) {
        //假设第一个元素的票数
       int count = 1;
        //假设第一个元素为当选人
       int candidate = nums[0];
       for(int i=0;i<nums.length; i++){
           //如果数组遍历过程中,有元素和当选人元素一样,就加一
           if(nums[i] == candidate){
               count++;
           }else{
                //如果没有就减一
               count--;
           }
            //如果票数为0的话就更换当选人
           if(count == 0){
               //更换当选人
               candidate = nums[i];
                //票数重新置为1
               count = 1;
           }
       }
       return candidate;
    }
}

leetcode原题: 169. 多数元素

解法分析

借助leetcode一位大佬的解释:

摩尔投票法也叫做同归于尽法,下面举一个三国的例子: 比如有甲、乙、丙三个军队进行厮杀,先假设甲的人数最多,然后发现最后甲和乙的人数全部阵亡,就只剩下丙了,那么这个丙就是人数最多的一个。

摩尔投票法:刚开始有甲乙丙三个候选人,谁都不知道是谁当选,因为票数都是 0,先假设数组的甲(这里是数组的第一个元素)为当选人,票数是 1,然后遍历整个数组,如果遇到甲的,票数就加一,如果遇到不是甲的,票数就减一,直到甲的票数为 0,甲的票数为 0 就更换候选人,然后继续比较,遍历到数组的最后一个元素就是当选人。然后票数等于 0 就更换当选人。

这道题的题目是假设数组是存在多数元素的,这个条件非常重要,也就是说这个数组中必定有元素是超过 n/2 的,也就是说用摩尔投票法找出来的众数一定是超过 n/2 的。

0

评论区