摩尔投票算法

文章目录

  • 什么是摩尔投票算法
    • 算法思想
  • 相关例题
  • 摩尔投票法的扩展题目
    • 解题思路
    • 代码奉上

什么是摩尔投票算法

摩尔投票法(Boyer-Moore Majority Vote Algorithm)是一种时间复杂度 为O(n),空间复杂度为O(1)的方法,它多数被用来寻找众数,它由 Robert S. Boyer 和 J Strother Moore 在1981年提出

算法思想

摩尔投票法的思想很简单,就是把寻找众数的过程当作一次选举大会,我们先选出一个候选元素 goal,然后他的票数为count,通过遍历数组,当前数组中的元素和候选元素相同时,count++,不同时,count–,当count==0时,则更换新的候选人。

摩尔投票算法的步骤 总结一下:
1.如果票数为0,将当前元素设为候选元素,并将票数设置为1。
2.如果当前元素等于候选元素,则票数加1。
3.如果当前元素不等于候选元素,则票数减1。

相关例题

169. 多数元素
在这里插入图片描述

class Solution {public int majorityElement(int[] nums) {int n=nums.length;int count = 0;int goal = 0;//候选人for(int i =0;i<nums.length;i++){if(count ==0){goal =  nums[i];count =1;}else if(nums[i] == goal){count++;}else{count--;}}return goal;}
}

摩尔投票法的扩展题目

229. 多数元素 II
在这里插入图片描述

解题思路

这道题和上面题有所不同,这个题可能会出现一到两个元素,也就是一到两个候选人的出现,而每个候选人的票数大于 总人数的三分之一即可
需要注意的是 我们除了想到当前元素与候选人1和候选人2是否相等时,还要想到不是他俩时,会怎么办

代码奉上

class Solution {public List<Integer> majorityElement(int[] nums) {List<Integer> res = new ArrayList<>();//返回的元素集合if(nums == null|| nums.length ==0){return res;}int goal1=0;//候选人1int goal2=0;//候选人2int count1 =0;//1的票数int count2 =0;//2的票数for(int num:nums){//开始遍历if(num ==goal1){//当数组和1相等时,1的票数+1,继续遍历count1++;continue;}if(num ==goal2){//当数组和2相等时,2的票数+1,继续遍历count2++;continue;}//当前值既不是1也不是2时,先判断两者的票数是否为0;如果为0,则更新候选人if(count1 ==0){goal1 =num;count1++;continue;}if(count2 ==0){goal2 =num;count2++;continue;}//若两者的票数都不为0,且当前数组都不是1,2时,两者票数--count1--;count2--;}//上一轮遍历是为了找出候选人,还要判断是否大于n/3,则需要重新遍历count1=0;count2=0;for(int num:nums){if(num ==goal1){count1++;}else if(num ==goal2){count2++;}}if(count1>nums.length/3){//当票数大于 n/3时,加入集合res.add(goal1);}if(count2>nums.length/3){res.add(goal2);}return res;}
}

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

Android liveData 监听异常,fragment可见时才收到回调记录

背景&#xff1a;在app的fragment不可见的情况下使用&#xff0c;发现注册了&#xff0c;但是没有回调导致数据一直未更新&#xff0c;只有在fragment可见的时候才收到回调 // 观察通用信息mLightNaviTopViewModel.getUpdateCommonInfo().observe(this, new Observer<Common…

什么是im即时通讯?WorkPlus im即时通讯私有化部署安全可控

IM即时通讯是Instant Messaging的缩写&#xff0c;指的是一种实时的、即时的电子信息交流方式&#xff0c;也被称为即时通讯。它通过互联网和移动通信网络&#xff0c;使用户能够及时交换文本消息、语音通话、视频通话、文件共享等信息。而WorkPlus im即时通讯私有化部署则提供…

Flat Ads:金融APP海外广告投放素材的优化指南

在当今全球化的数字营销环境中,金融APP的海外营销推广已成为众多金融机构与开发者最为关注的环节之一。面对不同地域、文化及用户习惯的挑战,如何优化广告素材,以吸引目标受众的注意并促成有效转化,成为了广告主们亟待解决的问题。 作为领先的全球化营销推广平台,Flat Ads凭借…

【学习笔记】无人机(UAV)在3GPP系统中的增强支持(二)-支持高分辨率视频直播应用

引言 本文是3GPP TR 22.829 V17.1.0技术报告&#xff0c;专注于无人机&#xff08;UAV&#xff09;在3GPP系统中的增强支持。文章提出了多个无人机应用场景&#xff0c;分析了相应的能力要求&#xff0c;并建议了新的服务级别要求和关键性能指标&#xff08;KPIs&#xff09;。…

c#调用c++ dll库报错System.BadImageFormatException

System.BadImageFormatException:“试图加载格式不正确的程序。 (异常来自 HRESULT:0x8007000B)” 1. dll需要选择release模式进行编译 2.选择相同位数&#xff0c;比如x64平台&#xff0c;c#也需要x64 3.不要设置c#不支持的函数供调用 比如&#xff1a; c可以输出到控制台…

5G-A通感融合赋能低空经济-RedCap芯片在无人机中的应用

1. 引言 随着低空经济的迅速崛起&#xff0c;无人机在物流、巡检、农业等多个领域的应用日益广泛。低空飞行器的高效、安全通信成为制约低空经济发展的关键技术瓶颈。5G-A通感一体化技术通过整合通信与感知功能&#xff0c;为低空网络提供了强大的技术支持。本文探讨了5G-A通感…

springboot上传图片

前端的name的值必须要和后端的MultipartFile 形参名一致 存储本地

蔚来汽车:拥抱TiDB,实现数据库性能与稳定性的飞跃

作者&#xff1a; Billdi表弟 原文来源&#xff1a; https://tidb.net/blog/449c3f5b 演讲嘉宾&#xff1a;吴记 蔚来汽车Tidb爱好者 整理编辑&#xff1a;黄漫绅&#xff08;表妹&#xff09;、李仲舒、吴记 本文来自 TiDB 社区合肥站走进蔚来汽车——来自吴记老师的演讲…

项目收获总结--本地缓存方案选型及使用缓存的坑

本地缓存方案选型及使用缓存的坑 一、摘要二、本地缓存三、本地缓存实现方案3.1 自己编程实现一个缓存3.2 基于 Guava Cache 实现本地缓存3.3 基于 Caffeine 实现本地缓存3.4 基于 Encache 实现本地缓存3.5 小结 四、使用缓存的坑4.1 缓存穿透4.2 缓存击穿4.3 缓存雪崩4.4 数据…

数学建模·非线性规划

整型规划 适用于一个变量或多个变量的值只能是整型的情况 整形规划的分类 0-1背包问题 对于一个物品来说&#xff0c;只有选和不选两种情况 表现为单下标&#xff0c;单变量问题 例&#xff1a;建设学校问题 对于每个学校来说只有选和不选两种情况&#xff0c;在数学上我们用…

轻松上手MYSQL:掌握MYSQL聚合函数,数据分析不再难

​&#x1f308; 个人主页&#xff1a;danci_ &#x1f525; 系列专栏&#xff1a;《设计模式》《MYSQL》 &#x1f4aa;&#x1f3fb; 制定明确可量化的目标&#xff0c;坚持默默的做事。 ✨欢迎加入探索MYSQL聚合函数之旅✨ &#x1f44b; 大家好&#xff01;文本学习和探…

微服务-注册中心

一. 分布式系统架构与微服务 分布式系统架构和微服务是现代软件开发中常见的两种概念&#xff0c;它们通常结合使用来构建灵活、可扩展和高效的应用程序。 分布式系统架构&#xff1a; 分布式系统架构是指将一个单一的应用程序或服务拆分成多个独立的部分&#xff0c;这些部分…

第一部分:C++入门

目录 前言 1、C关键字(C98) 2、命名空间 2.1、命名空间定义 2.2、命名空间的使用 3、C输入&输出 4、缺省参数 4.1、缺省参数的概念 4.2、缺省参数的分类 5、函数重载 5.1、函数重载的概念 5.2、C支持函数重载的原理 6、引用 6.1、引用的概念 6.2、引用特性 …

ensp实现ICMP重定向实验

1 概述 ICMP重定向报文是ICMP控制报文中的一种。在特定的情况下&#xff0c;当路由器检测到一台机器使用非优化路由的时候&#xff0c;它会向该主机发送一个ICMP重定向报文&#xff0c;请求主机改变路由。路由器也会把初始数据包向它的目的地转发。 2 实验复现 拓扑如下 PC1配…

RedHat Linux8 修改root管理员账户密码命令

RedHat Linux8 修改root管理员账户密码命令&#xff1a; sudo passwd root RedHat重置root管理员密码&#xff1a; 1. 查看Linux系统版本信息 cat /etc/redhat-release2. 重置密码 2.1 进入内核编辑界面 重启Linux系统并出现引导界面&#xff0c;按下键盘上的e键进入内…

ftp服务

文章目录 一、概述1.1 标准模式1.2 被动模式 二、FTP作用与工作原理2.1 FTP的作用和模式以及通信方式2.2 FTP工作原理与流程2.2.1 主动模式的工作原理2.2.2 被动模式的工作原理2.2.3 主动和被动模式的区别 三、搭建和配置FTP服务3.1 安装前准备工作3.1.1 关闭防火墙和增强型安全…

交易平台Zero Hash现已支持SUI交易

Zero Hash是一家领先的加密货币和稳定币基础设施平台&#xff0c;为包括Stripe、Shift4和Franklin Templeton在内的公司提供支持&#xff0c;现在也支持对SUI的访问。此举使Zero Hash的客户及其终端用户能够使用SUI。 提供API和SDK以及专注于无缝连接法币、加密货币和稳定币的…

Linux rsync文件同步工具

scp的不足 1. 性能问题 单线程传输 SCP只使用单线程进行传输&#xff0c;这意味着在传输大文件或大量小文件时&#xff0c;其传输速度和效率可能不如其他多线程工具。 无法压缩数据传输 SCP不支持内置的压缩机制&#xff0c;这在传输大文件时会导致带宽使用效率较低。 2.…

【Python 项目】类鸟群:仿真鸟群

类鸟群&#xff1a;仿真鸟群 仔细观察一群鸟或一群鱼&#xff0c;你会发现&#xff0c;虽然群体由个体生物组成&#xff0c;但该群体作为一个整体似乎有它自己的生命。鸟群中的鸟在移动、飞越和绕过障碍物时&#xff0c;彼此之间相互定位。受到打扰或惊吓时会破坏编队&#xf…

香橙派AIpro:体验强劲算力,运行ROS系统

文章目录 前言一、香橙派AIpro开箱及功能介绍1.1香橙派AIpro开箱1.2香橙派AIpro功能介绍 二、香橙派AIpro资料下载及环境搭建2.1资料下载2.2环境搭建2.3使用串口启动进入开发板2.4使用HDMI线接入屏幕启动 三、部署ROS系统四、香橙派AIpro的使用和体验感受 前言 本篇文章将带体…