力扣刷题篇——摩尔投票算法
友友们 大家好 我是你们的小王同学
今天给大家带来两道经典的摩尔投票算法的题型 小王的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时,将下⼀个元素作为当前查找元素,继续重复以上操作;当遍历结束时,当前查找元素则为⽬标元素
摩尔投票法分为两个核心步骤
- 投票阶段:投票人之间票数进行抵消
- 计数阶段:计算对抗结果最后剩下的那个候选人的票数是否有效
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
}
}
以上就是小王同学给大家带来的两道经典的摩尔投票法的例题
相关文章
- 【NLP基础】英文关键词抽取RAKE算法
- 《图解算法》系列学习(一)
- 无监督学习的12个最重要的算法介绍及其用例总结(附链接)
- 算法刷题笔记01:Array
- labuladong的算法小抄之js实现-第0章-学习算法和刷题的框架思维
- 每日算法刷题Day3-起始时间转换、二次方根、while连续输入、斐波那契思路
- 小白的diff算法试试水之旅
- java算法刷题00——数据结构基础知识回顾
- python使用sha算法进行加密
- 太全了!字节总监总结240道算法LeetCode刷题笔记
- 机器学习_knn算法_2
- 算法0基础刷题——日期计算
- 使用PyTorch实现简单的AlphaZero的算法(2):理解和实现蒙特卡洛树搜索
- 发现一位大佬的算法刷题笔记PDF
- 问题 1480: [蓝桥杯][算法提高VIP]模拟计算器
- Raft 共识算法2-领导者选举
- 不同的二叉搜索树算法详解编程语言
- AI 黑箱难题怎么破?基于神经网络模型的算法使机器学习透明化
- Redis中的LRU算法:如何优化缓存管理(redislru)
- PHP加密解密内部算法