大佬教程收集整理的这篇文章主要介绍了算法笔记:摩尔投票法,大佬教程大佬觉得挺不错的,现在分享给大家,也给大家做个参考。
问题引入:
给定一个大小为 n 的数组,找到其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
我们很轻松的想到暴力求解的方法:
定义两个指针i和j,i记录该位置的数字,j向后遍历
每遇到相等的数字就将计数器+1
如果计数器大于了n/2,就停止,并返回此时的i
但这种算法的时间复杂度较高,为O(n2),显然达不到题目的要求
所以,为了将这道题的时间复杂度降到O(n),我们可以使用摩尔投票法
摩尔投票法,是一个方便求众数的算法,其算法核心思想是:
我们可以想象有一个总统竞选,超过半数的当选总统
设有1,2,3三位总统竞选,选民将自己支持的总统的序号写在自己的牌子上
但不同的选民都互相看不顺眼,不顺眼的一对全部出去打架去了
这是出去打架后剩下的结果
可以观察到:
剩下的数字,绝对是那个超过了总数一半数字的
所以我们能轻易求出这个超过一半选票的总统是1
这就是我们理解这个算法的基础
int majorityElement(int* nums, int numsSize){
int count=0;
int ret=0;
for(int i=0;i<numsSize;i++)
{
if(count==0)//更新数字
{
ret=nums[i];
count=1;
}
else
{
if(ret==nums[i])//如果相等,计数器加一
{
count++;
}
else
{
count--;//不相等就减一
}
}
}
return ret;//最后记录的数字就是我们要求的众数
}
以上是大佬教程为你收集整理的算法笔记:摩尔投票法全部内容,希望文章能够帮你解决算法笔记:摩尔投票法所遇到的程序开发问题。
如果觉得大佬教程网站内容还不错,欢迎将大佬教程推荐给程序员好友。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。