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

发布于：2023-01-07 ⋅ 阅读:(638) ⋅ 点赞:(0)

这里是C语言刷题日志，整理了博主本人平时做练习遇到的问题以及相关的总结。不定时对文章内容更新优化，持续维护。

目录

一、题干

二、题解

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

思路

代码

2. 摩尔投票法拓展

例题-1  竞选社长

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

一、题干

力扣链接

169. 多数元素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 的元素。

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

 

代码

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

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

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

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

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

示例         "23335"

  1. 首先从字符 '2' 开始，count = 1 。
  2. 遇到 '3' ，由于'3'与'2'不同，则count -1 变为 0，'2' 的 count 被互拼消耗完。
  3. 再重新从剩下的 "335" 开始检查，这时保存字符 '3' ，遇到 '3' 则count +1， 遇到'5'则count -1。
  4. 最终 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  竞选社长

牛客网例题

BC40 竞选社长icon-default.png?t=M7J4https://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  求众数问题的变式

力扣链接

229. 多数元素 IIicon-default.png?t=M7J4https://leetcode.cn/problems/majority-element-ii/

注意

出现次数超过 \frac{n}{3} 的元素可能不止一个，最多只可能有两个。 

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

同理也可证明，出现次数超过  \frac{n}{2} 的元素个数最多只可能有一个。

//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;
}

值得一提：摩尔投票法求多数元素，可以推广到求出现次数多于  \frac{n}{k} 元素的情况。 

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布