力扣刷题篇——摩尔投票算法

 

 

友友们 大家好 我是你们的小王同学

 

今天给大家带来两道经典的摩尔投票算法的题型  如果觉得小王写的不错 麻烦给三连啦、

小王的csdn主页:(4条消息) 学好c语言的小王同学的博客_CSDN博客-c语言,力扣刷题领域博主

 

小王的gitee:

比特王信哲 (bitewang) - Gitee.com

 

        目录

          1.什么是摩尔投票法​

 2.例题​

        169 多数元素

         题目要求 :

         解题思路: 

        源码附上: 

1710.主要元素​

       题目描述:

        源码附上: 

1.什么是摩尔投票法

 


在⼀个⽆序数组中,存在⼀个数,它出现的次数⼤于数组长

度的⼀半。输出这个数
⼀、排序、遍历
⼆、摩尔投票法
摩尔投票算法是⼀种使⽤线性时间和常数空间查找⼤部分元素序列的算法。
最简单的形式就是,查找输⼊中重复出现超过⼀半以上(必须⼤于n/2,等于不算)的元素。如果序列中没有这种元素,算法不能检测到正确结
果,将输出其中的⼀个元素之⼀。
如果不能保证输⼊数据中有占有⼀半以上的元素,需要再遍历⼀下验证。
满⾜两个先决条件
1、出现超过⼀半以上(n/2)的元素有且只有⼀个
2、这个元素⼀定存在
算法步骤
我们维护⼀个局部变量作为当前查找元素,⼀个局部变量作为计数器,
当遍历开始的时候,此时计数(count)为0,则将数组第⼀个元素作为当前查找元素;
当遍历的元素与查找元素相等,计数加1;反之则-1
若当计数为0时,将下⼀个元素作为当前查找元素,继续重复以上操作;当遍历结束时,当前查找元素则为⽬标元素

 


 

 

 摩尔投票法分为两个核心步骤

  1.  投票阶段投票人之间票数进行抵消
  2. 计数阶段计算对抗结果最后剩下的那个候选人的票数是否有效

 2.例题

题目来自LeetCode

169 多数元素

题目要求 :

169. 多数元素 - 力扣(LeetCode) (leetcode-cn.com)

解题思路: 

1.我们先定义一个候选人 就是数组的第一个元素

2.然后定义一个记录候选人次数的count 初始化count

3.然后for循环遍历 如果有候选人那么我们的count就++,反之则- -

4.如果count为0时,就更换候选人

 

源码附上: 

class Solution {
    public int majorityElement(int[] nums) {
        int len=nums.length;
        
        int major=nums[0];//遍历第一个元素,候选人是2
        int count=0;
       
        for(int i=0;i<len;i++){
             
             //如果数组中还有2的话我们的count就++;
             if(nums[i]==major){
                 count++;
             }else{
                 //如果没有就减1
                 count--;
             }
             //如果count=0的时候就更换候选人
             if(count==0){
                //更换候选人
                major=nums[i];//重新赋值major
                //票数重置为1
                count=1;

             }
        }
        return major;



    }
}

这种情况只能对于多数存在的情况下 比如[4,5,6]major等于6显然是错误的 

所以对于不一定存在多数的情况下 我们需要在求出major的情况下 在遍历一遍 

统计count的次数是否大于数组长度的一半

 1710.主要元素

 题目描述:

源码附上: 

class Solution {
    public int majorityElement(int[] nums) {
        int len=nums.length;
        
        int major=nums[0];//遍历第一个元素,候选人是2
        int count=0;
       
        for(int i=0;i<len;i++){
              if(count==0){
                //更换候选人
                major=nums[i];//重新赋值major
                //票数重置为1
               

             }
             
             //如果数组中还有2的话我们的count就++;
             if(major==nums[i]){
                 count++;
             }else{
                 //如果没有就减1
                 count--;
             }
             //如果count=0的时候就更换候选人
             
        }
        count=0;
     
        for(int num:nums){ //遍历一遍 记录count的次数
            if(num==major){
                count++;
            }
        }
        return(count<=len/2)?-1:major; //根据条件判断如果长度超过数组长度的一半 就输出major

        反之则输出-1



    }
}

 以上就是小王同学给大家带来的两道经典的摩尔投票法的例题

友友们如果觉得小王写的不错就三连支持一下啦

码字不易 谢谢大家


原文连接:https://blog.csdn.net/weixin_59796310/article/details/124485896

相关推荐

翟佳:高可用、强一致、低延迟——BookKeeper的存储实现

管正雄:基于预训练模型、智能运维的QA生成算法落地

814. 二叉树剪枝 : 简单递归运用题

【综合笔试题】难度 3.5\u002F5,多解法热门二叉树笔试题

【java刷算法】牛客—剑指offer3栈、数组、递归、二分法的初步练习

leetcode 2342. Max Sum of a Pair With Equal Sum of Digits (python)

22张图带你深入剖析前缀、中缀、后缀表达式以及表达式求值

随机数索引(一题双解)【Leetcode每日(4.25)一题】C++

1260. 二维网格迁移 : 简单构造模拟题

坚持用C++刷牛客题(剑指offer专题)

日拱一卒,麻省理工教你信息安全和密码学

C语言——三种方式实现学生信息管理

快速排序及优化

萌新也能看懂的KMP算法

简答一波 HashMap 常见八股面试题 —— 算法系列(2)

素数算法(Prime Num Algorithm)

必须收藏!双目立体匹配算法:Patch Match Stereo实用详解教程

有哪些高质量的自学网站?

731. 我的日程安排表 II : 线段树(动态开点)的两种方式

LeetCode周赛302,这也太卷了,20分钟ak也只有300名……