DAY-3 | 摩尔投票法:巧求众数问题

简介: LeetCode 链接:[Majority Element](https://leetcode.cn/problems/majority-element/)。这道题要求找到数组中出现次数超过数组长度一半的元素,也称为众数。文章介绍了使用摩尔投票法来解决此类问题,这种方法通过相互抵消的方式高效地找到多数元素。首先假设第一个元素是众数,然后遍历数组,遇到相同元素计数加一,不同元素计数减一,计数为零时更换假设的众数。最后计数不为零的元素即为众数。此外,还讨论了摩尔投票法的拓展应用和暴力统计的解法。

一、题干


力扣链接


https://leetcode.cn/problems/majority-element/



二、题解


本题是求众数的经典例题,即:求数组中的多数元素。我们需要找的是在数组中出现次数大于 n/2 次的元素(数字)。


最容易想到的方法是暴力统计,即从头到尾遍历数组元素,分别统计并保存每一个元素出现的次数。但这个办法不太现实,实现起来相对繁琐,因此在这里不赘述。本文主要介绍摩尔投票法在众数问题中的应用。


1. 摩尔投票法 -- 互拼消耗


思路


摩尔投票法的核心思想在于互拼消耗


首先我们考虑最基本的摩尔投票问题,比如找出一组数字序列中出现次数大于总数一半的数字(并且假设这个数字一定存在)。我们可以利用反证法证明这样的数字只可能有一个。


假设投票是这样的:


[A, C, A, A, B],A 和 B 和 C 分别代表三个候选人。每一张票都与它后面的一张票进行对抗,若前后两张票相同,则增加这张票所代表的候选人的“可抵消票数”;若后一张票与该票不同,则互相抵消,即该票所代表的候选人的“可抵消票数”-1。


于是投票便有如下过程:


  • 第一张票(A)与第二张票(C)进行对坑,由于二者票不同,则互相抵消;
  • 然后,第三票(A)与第四票(A)进行对坑,二者票相同,则候选人 A 的可抵消票数+1;
  • 接着,这个候选人 A 拿着可抵消票数再与第五张票(B)对坑,二者票不同,则再次互相抵消掉,即候选人(A)的可抵消票数 -1。


以上是摩尔投票法实现机制 —— 互拼消耗的初步演示。概括而言,摩尔投票法分为两个阶段:抵消阶段计数阶段


  • 抵消阶段:若相对抗的两票不同,则减少一次可抵消的次数;若相对抗的两票相同,则增加一次可抵消的次数;
  • 计数阶段:在所有元素统计完毕后,最后得到的抵消计数不为 0 的候选人,是票数最多的候选人。为了验证,需遍历一次,统计票数以确定结果。


摩尔投票法最多消耗 O(2n) 的时间,属于 O(n) 的线性时间复杂度,另外空间复杂度属于常量级。需要注意的是,摩尔投票法只能筛选出数组中票数排在前 k 的元素。


当题目要找出出现次数多于  的元素时,在互拼消耗筛选出元素后还要将筛选出的这些元素重新统计检查一遍票数,看它们是否大于 票。这就是还有一个计数阶段存在的原因。


代码


从下标为 0 的首字符开始。


我们先假设首字符就是要找的出现次数最多的那个元素(将首元素保存),并初始化计数 count 为1。


随后向后遍历,若遇到相同的数字则计数 +1,遇到不同的数字则计数 -1,这就是互拼消耗。


当计数 count 为 0 时,表示本次的互拼完毕,需要从下一个字符重新开始互拼(再保存下一个字符),重复上述过程。


由于“出现次数大于 n/2 的这个元素”数量是更多的,因此即使走到最后,该元素的 count 也不会被抵消完。即:在计数 count 不为 0 时,走到末尾时所保存的元素就是个数超过 n/2 的元素。


示例         "23335"


首先从字符 '2' 开始,count = 1 。

遇到 '3' ,由于'3'与'2'不同,则count -1 变为 0,'2' 的 count 被互拼消耗完。

再重新从剩下的 "335" 开始检查,这时保存字符 '3' ,遇到 '3' 则count +1, 遇到'5'则count -1。

最终 count 为 1 (不为 0),而走到末尾保存的字符为 '3' 。因此 '3' 即所求的多数元素。


int majorityElement(int* nums, int numsSize){
    int count = 1;     //初始化计数器count为1
    int tmp = nums[0];     //先保存数组首元素的值
 
    for (int i = 1; i < numsSize; i++) { 
        if (tmp == nums[i]){    //与保存的元素相同,则计数+1 
            count++; 
        } else {    //与保存的元素不同,则计数-1 
            count--; 
            if (count == 0){     //计数为0表示保存的元素不是最多的元素,换下一个
                tmp = nums[i + 1];    //重新保存
            } 
        } 
    }
 
    return tmp;    //返回走到最后且计数不为0的元素
}


2. 摩尔投票法拓展


例题-1  竞选社长


牛客网例题


https://www.nowcoder.com/practice/45a30e3ef51040ed8a7674984d6d1553



代码


代码1 -- 摩尔投票法


#include<stdio.h>
 
int main(){
    char arr[100];
    gets(arr);
    char tmp = arr[0];    //保存首元素
    char* cur = arr+1;    //从第二个元素开始互拼消耗
    
    int count = 1;    //初始化count
 
    while(*cur != '0'){
        if(tmp == *(cur)){    //所保存的元素等于当前元素
            count++;
        }else{    //所保存的元素不等于当前元素
            count--;    //抵消
            if(count == 0){    //抵消完了,换下一个元素保存
                tmp = *(cur+1);
            }
        }
        cur++;
    }
 
    if(count == 0){
        printf("E");
    }else{
        printf("%c",tmp);
    }
    return 0;
}


代码2 -- 摩尔投票法(当只有两个元素时,可以有另一种写法,但思想类似)


代码3 -- 暴力统计法(由于本题只有A和B两种状况,因此容易实现)


#include <stdio.h>
 
int main()
{
    char arr[100] = {0};
    gets(arr);
    int i = 0;
    int count_a = 0;
    int count_b = 0;
    while(arr[i] != '0')
   {
        if(arr[i] == 'A')
       {
            count_a ++;
       }
        else if(arr[i] == 'B')
       {
            count_b ++;
       }
        i++;
   }
    if(count_a > count_b)
        printf("A");
    else if(count_a < count_b)
        printf("B");
    else
        printf("E");
    return 0; 
}


代码4 -- 以getchar()获取字符并多组输入


int main()
{
    char arr[100] = {0};
    int ch = 0;
    int flag = 0;
    //如果getchar获取了
    while(((ch=getchar()) != '0') && ch != EOF)
   {
        if(ch == 'A')
       {
            flag++;
       }
        else if(ch == 'B')
       {
            flag--;
       }
   }
    if(flag>0)
        printf("A");
    else if(flag<0)
        printf("B");
    else
        printf("E");
    return 0; 
}


例题-2  求众数问题的变式


力扣链接

https://leetcode.cn/problems/majority-element-ii/




注意


出现次数超过  的元素可能不止一个,最多只可能有两个。


反证法:当数组中出现次数超过  的元素个数有 3 个及以上时,它们出现的总次数大于等于了 3 ×  即n,也就是说如果出现次数超过  的元素个数 > 2 时,它们出现的总次数超过了元素总个数n,这是矛盾的。


同理也可证明,出现次数超过   的元素个数最多只可能有一个。


//C语言接口型实现
int* majorityElement(int* nums, int numsSize, int* returnSize){
    int cand1 = nums[0];    int count1 = 0;    //下面从下标0开始遍历,故初始化count为0
    int cand2 = nums[0];    int count2 = 0;
    
    //1-互拼阶段
    for (int i = 0; i < numsSize; i++)    //遍历数组元素
    {
        if (nums[i] == cand1){
            count1++;
            continue;
        }
        if (nums[i] == cand2){
            count2++;
            continue;
        }
 
        if (count1 == 0){
            cand1 = nums[i];
            count1++;
            continue;
        }
        if (count2 == 0){
            cand2 = nums[i];
            count2++;
            continue;
        }
        
        //都不一样,则抵消
        count1--;    
        count2--;
    }
    
    //2-计数阶段:检查筛选出来的cand1和cand2的票数是否多于 n/3
    count1 = 0;
    count2 = 0;
    for (int i = 0; i < numsSize; i++){
        if (nums[i] == cand1){
            count1++;
        }
        else if (nums[i]==cand2){
            count2++;
        }
    }
 
    int *res = (int*)malloc(sizeof(int)*2);    //开辟返回数组,数组长度设定为2
 
    if (count1 > numsSize/3 && count2 > numsSize/3){
        res[0] = cand1;
        res[1] = cand2;
        *returnSize = 2;
        return res;
    } else if (count1 > numsSize/3) {
        res[1] = cand1;
        *returnSize = 1;
        return &res[1];
    } else if (count2 > numsSize/3) {
        res[1] = cand2;
        *returnSize = 1;
        return &res[1];
    }
 
    *returnSize = 0;
    return nums;
}


值得一提:摩尔投票法求多数元素,可以推广到求出现次数多于   元素的情况。

相关文章
|
1月前
|
存储 算法
摩尔投票的原理详解
摩尔投票的原理详解
53 1
|
1月前
|
算法 测试技术 C#
C++二分向量算法:最多可以参加的会议数目 II
C++二分向量算法:最多可以参加的会议数目 II
|
11月前
|
算法 JavaScript Android开发
LeetCode 周赛上分之旅 #33 摩尔投票派上用场
学习数据结构与算法的关键在于掌握问题背后的算法思维框架,你的思考越抽象,它能覆盖的问题域就越广,理解难度也更复杂。在这个专栏里,小彭与你分享每场 LeetCode 周赛的解题报告,一起体会上分之旅。
57 0
|
算法 C++
【每日算法Day 98】慈善赌神godweiyang教你算骰子点数概率!
【每日算法Day 98】慈善赌神godweiyang教你算骰子点数概率!
|
人工智能 算法 Java
摩尔投票法
摩尔投票法
160 0
|
算法
算法:奶牛慢跑
题目: 奶牛们又出去锻炼蹄子去了! 有 N 头奶牛在无限长的单行道上慢跑。 每头奶牛在跑道上开始奔跑的位置都不相同,一些奶牛的奔跑速度也可能不同。
96 0
【LeetCode169】多数元素(摩尔投票法)
先用sort排序后,因为定义的“多数元素”是在数组中出现次数大于n/2的元素,所以可以返回下标为n/2的数组元素即所求。 用sort的时间复杂度就是O(nlogn)而非O(n)了。
76 0
【LeetCode169】多数元素(摩尔投票法)