想要精通算法和SQL的成长之路 - 摩尔投票法的运用

想要精通算法和SQL的成长之路 - 摩尔投票法的运用

  • 前言
  • 一. 多数元素
    • 1.1 摩尔投票法
  • 二. 多数元素II
    • 2.1 分析

前言

想要精通算法和SQL的成长之路 - 系列导航

一. 多数元素

原题链接
在这里插入图片描述

1.1 摩尔投票法

简单来说,假设数组 num 的众数是 x,数组长度为n
有两个推论:

  • 我们有一个票数和为sum,若记众数的票数为 +1 ,非众数的票数为 −1 ,则一定有所有数字的票数和 sum >0
  • 如果数组的前 m 个数字的票数和为0,那么剩余的(n-m) 个数字的票数和一定 > 0,并且后面(n-m)个数字中的众数依旧是x

那么针对本题目,求得的是多数元素,其出现次数超过数组元素个数的一半。思路如下:

  • 我们设置当前众数为:res。初始化为数组第一元素。
  • 设置当前票数和为:vote。初始化为0
  • 遍历数组:如果票数和为0,更新众数为当前元素。
  • 每次遍历,都对票数做统计,是众数,则+1,否则-1。

结果如下:

public int majorityElement(int[] nums) {
    int res = nums[0], vote = 0;
    for (int num : nums) {
        if (vote == 0) {
            res = num;
        }
        vote += (res == num) ? 1 : -1;
    }
    return res;
}

二. 多数元素II

原题链接
在这里插入图片描述
在原题的基础上,不再是求出现次数超过2分之一的多数元素了。而是三分之一。即本题的返回个数最多有两个。

2.1 分析

我们这里这里假设:有两个(并且最多只有两个)符合题目条件的元素:x 和 y。他们的票数分别是v1 和 v2。

  1. 利用摩尔投票法,确定两个候选数。因为我们这里假设的是2个都满足条件,但是实际情况可能只有一个或者没有。这里只是求得:出现次数最多的前两个数是哪几个(实际他们的出现次数却不知道)
  2. 最后再对这两个候选人做计数统计,统计他们分别出现的次数是多少,是否满足题目要求。

阶段一:摩尔投票阶段,决定出现次数最多的前两个数:

// 初始化两个候选数和对应票数
int x = nums[0], y = nums[0];
int v1 = 0, v2 = 0;
// 摩尔投票,求得出现次数最多的两个数
for (int num : nums) {
    // 如果当前数和x一样
    if (x == num) {
        v1++;
        continue;
    }
    // 如果当前数和x一样
    if (y == num) {
        v2++;
        continue;
    }
    // 第一个候选票数为0了,那么当前数认定为第一个候选数
    if (v1 == 0) {
        x = num;
        v1++;
        continue;
    }
    // 第二个候选 同理
    if (v2 == 0) {
        y = num;
        v2++;
        continue;
    }
    // 否则,都不满足两个候选,两个候选的票数同时-1
    v1--;
    v2--;
}

这时候,我们拿到票数最多的两个元素,x和y。他们可能是同一个元素,也可能不是同一个元素。

接下来进入阶段二,统计票数阶段:

// 阶段二:统计票数阶段
v1 = 0;
v2 = 0;
for (int num : nums) {
    if (num == x) {
        v1++;
    } else if (num == y) {
        v2++;
    }
}

注意:不能这么写:(两个数如果是同一个,那就重复了)

for (int num : nums) {
    if (num == x) {
        v1++;
    }
    if (num == y) {
        v2++;
    }
}

最后,判断他们的出现次数是否满足条件,满足则加入结果集,所有代码如下:

public List<Integer> majorityElement(int[] nums) {
    ArrayList<Integer> res = new ArrayList<>();
    if (nums == null || nums.length == 0) {
        return res;
    }
    // 初始化两个候选数和对应票数
    int x = nums[0], y = nums[0];
    int v1 = 0, v2 = 0;
    // 摩尔投票,求得出现次数最多的两个数
    for (int num : nums) {
        // 如果当前数和x一样
        if (x == num) {
            v1++;
            continue;
        }
        // 如果当前数和x一样
        if (y == num) {
            v2++;
            continue;
        }
        // 第一个候选票数为0了,那么当前数认定为第一个候选数
        if (v1 == 0) {
            x = num;
            v1++;
            continue;
        }
        // 第二个候选 同理
        if (v2 == 0) {
            y = num;
            v2++;
            continue;
        }
        // 否则,都不满足两个候选,两个候选的票数同时-1
        v1--;
        v2--;
    }

    // 阶段二:统计票数阶段
    v1 = 0;
    v2 = 0;
    for (int num : nums) {
        if (num == x) {
            v1++;
        } else if (num == y) {
            v2++;
        }
    }
    // 最后看看是否超过了三分之一
    if (v1 > nums.length / 3) {
        res.add(x);
    }
    if (v2 > nums.length / 3) {
        res.add(y);
    }
    return res;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/162861.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

基于Java+SpringBoot+Vue3+Uniapp+TypeScript(有视频教程)前后端分离健身预约系统设计与实现

博主介绍&#xff1a;✌全网粉丝5W&#xff0c;全栈开发工程师&#xff0c;从事多年软件开发&#xff0c;在大厂呆过。持有软件中级、六级等证书。可提供微服务项目搭建与毕业项目实战&#xff0c;博主也曾写过优秀论文&#xff0c;查重率极低&#xff0c;在这方面有丰富的经验…

UE5制作场景时的小技巧和注意事项

UE5制作场景时的小技巧和注意事项 一、场景相关 1.1灯光 1.1.1构建完光照,发现场景都是黑的 可能是所有灯光是静态灯光,把skylight改为动态,如果改完之后还是黑色的,那就在构建一次,就应该没问题了 1.1.2场景中有多个动态光会造成阴影闪烁 需要将skylight变为固定 1…

C语言之for while语句详解

C语言之for while语句详解 文章目录 C语言之for while语句详解简介1 while语句1.1while语句的格式1.2 while语句的实践 2 for2.1 for语句格式2.2 for循环的实践 3 do while3.1 do while语句格式3.2 do while循环的实践 3 循环中break和continue3.1 while语句中的break和continu…

STM32与ZigBee无线通信技术在工业自动化中的应用

工业自动化是指利用电子技术、计算机技术和通信技术等手段&#xff0c;对工厂、设备和生产过程进行自动化控制和管理的过程。在工业自动化中&#xff0c;可靠的无线通信技术对于实时数据的传输和设备的协同控制至关重要。本文将介绍STM32微控制器与ZigBee无线通信技术在工业自动…

君正X2100 读取CHIP_ID

每个处理器会有一个唯一的ID&#xff0c;这个ID可用做产品序列号&#xff0c;或其它。 X21000的CHIP_ID存放于芯片内部的efuse中&#xff0c;efuse是一次性可可编程存储器&#xff0c;初始值为全0&#xff0c;只能将0改为1&#xff0c;不能将1改为0。芯片出厂前会被写入一些信…

WPF中行为与触发器的概念及用法

完全来源于十月的寒流&#xff0c;感谢大佬讲解 一、行为 (Behaviors) behaviors的简单测试 <Window x:Class"Test_05.MainWindow"xmlns"http://schemas.microsoft.com/winfx/2006/xaml/presentation"xmlns:x"http://schemas.microsoft.com/winf…

STL简介

> 作者简介&#xff1a;დ旧言~&#xff0c;目前大二&#xff0c;现在学习Java&#xff0c;c&#xff0c;c&#xff0c;Python等 > 座右铭&#xff1a;松树千年终是朽&#xff0c;槿花一日自为荣。 > 目标&#xff1a;了解c中的STL库 > 毒鸡汤&#xff1a;路难行&a…

22款奔驰S450L升级流星雨大灯 感受最高配的数字大灯

“流星雨”数字大灯&#xff0c;极具辨识度&#xff0c;通过260万像素的数字微镜技术&#xff0c;实现“流星雨”仪式感与高度精确的光束分布&#xff1b;在远光灯模式下&#xff0c;光束精准度更达之前84颗LED照明的100倍&#xff0c;更新增坡道照明功能&#xff0c;可根据导航…

UE 程序化网格 计算横截面 面积

首先在构造函数内加上程序化网格&#xff0c;然后复制网格体到程序化网格组件上&#xff0c;将Static Mesh&#xff08;类型StaticMeshActor&#xff09;的静态网格体组件给到程序化网格体上 然后把StaticMesh&#xff08;类型为StaticMeshActor&#xff09;Instance暴漏出去 …

原型网络Prototypical Network的python代码逐行解释,新手小白也可学会!!-----系列6 (承接系列5)

文章目录 一、原始代码---随机采样和评估模型二、详细解释分析每一行代码 一、原始代码—随机采样和评估模型 def randomSample(self,D_set): #从D_set随机取支持集和查询集&#xff08;20个类中的其中一个类&#xff0c;shape为[20,105,105]&#xff09;index_list list(ran…

复旦大学EMBA深度链接深圳科创产业:聚焦智联,产融未来

作为科创成就的经济大区&#xff0c;深圳南山区通过跨界创新研发生态链条&#xff0c;领跑科创产业创新&#xff0c;以187.5平方公里的面积&#xff0c;雄踞着204家上市公司&#xff0c;地均生产总值产出达到了40.7亿元&#xff0c;相当于每平方公里出产超过1家上市公司&#x…

Java项目实战《苍穹外卖》 二、项目搭建

当我痛苦地站在你的面前 你不能说我一无所有 你不能说我两手空空 系列文章目录 苍穹外卖是黑马程序员2023年的Java实战项目&#xff0c;作为业余练手用&#xff0c;需要源码或者课程的可以找我&#xff0c;无偿分享 Java项目实战《苍穹外卖》 一、项目概述Java项目实战《苍穹外…

B-2:Linux系统渗透提权

B-2:Linux系统渗透提权 服务器场景:Server2204(关闭链接) 用户名:hacker 密码:123456 1.使用渗透机对服务器信息收集,并将服务器中SSH服务端口号作为flag提交; 使用nmap扫描,发现ssh服务端口为2283 Flag:2283 2.使用渗透机对服务器信息收集,并将服务器中…

复合、委托、继承

1. 单例模式 静态实例对象在getInstance函数中定义&#xff0c;这样只有在调用函数时才会生成对象 2. 复合 1. 类中封装另一个类某些功能&#xff1b; 2. 构造、析构的调用过程 指明了复合中如何调用被包含类的构造函数&#xff0c;可以直接写在初始化列表位置&#xff1b; 3.…

剑指JUC原理-19.线程安全集合

&#x1f44f;作者简介&#xff1a;大家好&#xff0c;我是爱吃芝士的土豆倪&#xff0c;24届校招生Java选手&#xff0c;很高兴认识大家&#x1f4d5;系列专栏&#xff1a;Spring源码、JUC源码&#x1f525;如果感觉博主的文章还不错的话&#xff0c;请&#x1f44d;三连支持&…

Spring Cloud -熔断器Hystrix

为什么需要服务降级或熔断 微服务架构与传统架构的一个显著区别就是服务变多了&#xff0c;任何一个服务调用失败、或者服务不可用&#xff0c;都会对整个应用造成影响。比如前段时间阿里云整体业务不可用&#xff0c;有多方猜测就是阿里云的某一个关键服务不可用导致的。 服…

火星探测器背后的人工智能:从原理到实战的强化学习

目录 一、引言二、强化学习基础强化学习的基本概念主要算法概述Q-Learning 示例代码 环境建模与奖励设计 三、火星探测器任务分析任务需求与挑战探测器环境建模目标设定与奖励机制层层递进的关系 四、强化学习模型设计模型架构概述DQN架构核心组件&#xff1a; 状态、动作与奖励…

RT-Thread基于STM32H743的网络通信调试

使用STM32H743开发网络通信&#xff0c;本以为会很简单&#xff0c;实际却遇到好多问题&#xff0c;记录一下&#xff0c;以备后续查看。 1.新建工程&#xff0c;系统版本选择的是4.1.1&#xff0c;芯片型号是STM32H743IIK6. 2.修改系统时钟&#xff0c;使用外部25MHz晶振&…

C++类与对象(1)—初步认识

目录 一、面向过程和面向对象 二、类 1、定义 2、类的两种定义方式 3、访问限定符 4、命名规范化 5、类的实例化 6、计算类对象的大小 7、存储方式 三、this指针 1、定义 2、存储位置 3、辨析 四、封装好处 一、面向过程和面向对象 C语言是面向过程的&#xf…

记录联系ThinkPad T490扬声器无声音但插耳机有声音的解决办法

型号&#xff1a;联想ThinkPad T490&#xff0c;系统Win10 64位。 现象&#xff1a;扬声器无声音&#xff0c;插耳机有声音。且右下角小喇叭正常&#xff0c;设备管理器中驱动显示一切也都正常&#xff08;无黄色小叹号&#xff09;。 解决办法&#xff1a; 尝试了各种方法&a…