摩尔投票的一般性方法

前言

本文将介绍摩尔投票的一般性方法。

二分之一

让我们从最简单的开始，如何求出数组中所有出现次数在二分之一以上的元素？

参考题目：多数元素I

首先，一个数组里面最多只能有一个出现次数大于总长度一半的数。因此，本题可能满足条件的元素最多只有一种。

1，若存在一种元素满足条件

我们设满足条件的元素为val，将数组分为两个集合，一个是由所有的val组成的集合A，另一个是由剩下的元素组成的集合B。

假设val的数量刚好占了1/2，则两个集合的数目相等，我们从集合A、B中分别拿出一个元素，让这两个元素消除，循环往复，这个数组将被消除的干干净净。

事实是，集合A的元素数量多于1/2，集合B的元素数量少于1/2，如果我们从集合A、B中各拿一个元素消除，循环往复，那么剩下的元素一定是集合A中的val。

因此，我们只需要每次从数组中拿出两个元素，保证其中一个是val，另一个不是val，然后让他们循环消除，最后剩下的就是我们要求的val了。

但是，我们并不知道集合A、B在数组中的位置，自然也不能准确地将他们拿出来，我们只能通过从前往后遍历的方式检测数组中的元素。

因此，我们暂时设val为数组中的第一个元素，这样我们就拿到了val，只需要找到一个与val不相等的元素，就可以完成一次消除了。

于是从前往后遍历，我们将这时的nums【i】分为两种情况：

1. nums【i】与val相等。
2. nums【i】与val不相等。

如果是第一种情况，显然不满足我们之前推导的两个元素消除的条件，但是，我们也不能无视当前的numsi。

因此，设变量num，统计val出现的次数。这时如果出现第一种情况，就让num+1，当val被消除时，可以补上一个相同的数，同时让num-1。

如果是第二种情况，就让num-1，一旦出现num等于0的情况，就代表当前的val已经被暂时消除干净了，需要马上更换一个val，同时将num设为1。

这时有同学就提出一个问题，更换的val并不一定最终的答案啊？

是这样没错，我们最开始设置的val，也不一定是最终的答案，那我们为什么要这样做呢？

因为，我们需要一个集合B中的元素才能进行一次消除，而集合B中的元素数量根本连1/2都达不到，所以val被消除的次数，不会超过1/2。而集合A的元素数量超过了1/2，所以当循环结束，集合A一定会有剩余。即使更换的val不一定是最终答案，后面“真正的”val也会将他们替换下来。

你可以这样理解，当并非最终答案的一个元素成为了val，那么“真正的”val就被归纳为集合B中的元素了，此时的集合B_plus，是原来的集合B与集合A之和，其数量绝对远远超过原来的集合B。况且，集合B中的元素并非全部相等，这个假冒的答案不一定有那么多的“同伙”来帮它撑num的数值，就算集合B元素全部相等，也依然没有真正的val的数量多，因此，这个假冒的元素一定会被真正的元素挤下来。

这时又有同学要问了，如果在数组遍历结束的最后一刻，val从最终答案变成别的数了怎么办？

首先，如果数组存在一个满足条件的元素，因为集合A的元素数量比C的多，这种情况一定不会发生，如果发生了，那就一定是接下来要讲的，不存在满足条件的元素的讨论。

2，若不存在元素满足条件

如果没有元素满足条件，解决方法很简单，只需要遍历一次就行了，统计这个val出现的次数，此时的时间复杂度依然是O（n）。

如果题目告诉你一定存在满足条件的数，那么直接返回val即可；如果题目告诉你不一定存在满足条件的数，遍历一遍即可。

代码实现

在这里我展示参考题目的提交通过代码，参考题目中已经规定数组中一定存在一个满足条件的元素，因此你可以省略下面的次数统计。

int majorityElement(int* nums, int numsSize)
{
    int val = 0;
    int num = 0;

    int i = 0;
    for (i = 0; i < numsSize; i++) 
    {
        if(num==0)
        {
            val=nums[i];
            num=1;
        }
        else if(val==nums[i])
        {
            num++;
        }
        else if(val!=nums[i])
        {
            num--;
        }
        
    }
    
    int count=0;//在参考题目中可以省略
    for(i=0;i<numsSize;i++)
    {
        if(nums[i]==val)
        {
            count++;
        }
    }
    if(count>numsSize/2)
        return val;
    else 
        return;
}

三分之一

参考题目：多数元素II

首先，2个大于1/3的数相加，其结果一定大于2/3，因此，这题里出现次数超过1/3的元素最多只有两种。

1，若存在两种元素满足条件

我们将这两种元素分别设为val1，val2，然后将数组分为三个集合，第一个是val1的集合A，第二个是val2的集合B，第三个是剩余元素的集合C。假设val1和val2都刚刚好占了1/3，那么我们从ABC中分别取出一个元素，然后将他们消除，循环往复，这个数组将被消除的干干净净。

事实是，集合A的元素数量大于1/3，集合B的元素数量也大于1/3，集合C的元素数量少于1/3，如果我们在ABC中各拿一个元素，循环消除，那么最先消除的集合一定是C。

因此，我们只需要每次在数组中拿出三个元素，保证其中一个是val1，一个是val2，另一个是集合C中的元素，然后让他们循环消除，最后剩下的元素一定就是我们要求的val1和val2。

但是，我们并不知道集合ABC在数组中的位置，自然也不能准确地将他们拿出来，我们只能通过从前往后遍历的方式检测数组中的元素。

因此，设val1为数组的第一个元素，val2是数组从前往后数第一个和val1不同的元素，这样我们就拿到了val1和val2，只需要找出第三个元素，于是从前往后遍历，假设数组为nums，遍历使用的工具变量设为i，我们将这时的nums【i】分为三种情况：

1. nums【i】与val1相等。
2. nums【i】与val2相等。
3. nums【i】与val1和val2都不相等。

如果是第一种和第二种情况，显然不满足我们之前推导的三个元素消除的条件，但是，我们也不能无视当前的nums【i】。

因此，设num1、num2，分别统计val1、val2出现的次数。这时如果出现第一种或第二种情况，就让对应的num+1，这样当对应的val被消除时，可以补上一个相同的数，同时让对应的num-1。

如果是第三种情况，让num1和num2都各自-1，一旦出现num等于0的情况，就代表当前对应的val已经被暂时消除干净了，需要马上更换一个val，因为有两个val的存在，所以你在更换一个val的时候需要注意，新的val不能和另外一个val相等，同时将被更换的val的num设为1。

这时有同学就提出一个问题，更换的val并不一定最终的答案啊？

是这样没错，我们最开始设置的val1和val2，也不一定是最终的答案，那我们为什么要这样做呢？

因为，我们需要一个集合C中的元素才能进行一次消除，而集合C中的元素数量根本连1/3都达不到，所以val1和val2被消除的次数，不会超过1/3。而集合A和B的元素数量超过了1/3，所以当循环结束，集合A与B一定会有剩余。即使更换的val不一定是最终答案，后面“真正的”val也会将他们替换下来。

你可以这样理解，当并非最终答案的一个元素成为了val1，那么“真正的”val1就被归纳为集合C中的元素了，此时的集合C_plus，是原来的集合C与集合A之和，其数量绝对远远超过原来的集合C。况且，集合C中的元素并非全部相等，这个假冒的答案不一定有那么多的“同伙”来帮它撑num的数值，就算集合C元素全部相等，也依然没有真正的val1的数量多，因此，这个假冒的元素一定会被真正的元素挤下来。

这时又有同学要问了，如果在数组遍历结束的最后一刻，val从最终答案变成别的数了怎么办？

首先，如果在数组存在两种满足要求的元素，因为集合A和B的元素数量都比集合C的数量多，这种情况一定不会发生，如果发生了，那就一定是接下来要讲的，只存在一个或没有满足要求的元素的讨论。

2，若只存在一个或没有元素满足条件

我们假设val1满足条件，val2不满足条件，则上述情况的发生，是val2在遍历结束前被清除干净了，而val1因为数量超过了1/3，又因为消除次数小于1/3，所以依然保留。

又或者两个val都不满足条件，都被替换成了别的数。

对于这种情况，不必太过苦恼，解决方法很简单，遍历一次就行了，统计这两个数出现的次数，此时的时间复杂度依然是O（n）。

如果题目告诉你满足条件的数一定有两个，你可以直接返回这两个数；如果题目告诉你满足条件的数只有一个，你可以比较这两个数的大小，返回较大的数即可。

代码实现

对于三分之一的问题，代码实现时有一个特殊情况，即数组全部元素都等于val2的初始值，val1在进入循环时被赋为该值，num1的长度最终变为数组长度，此时val1与val2相等，需要在结束时判断两者是否相等。

在此我展示参考题目的通过代码。

int* majorityElement(int* nums, int numsSize, int* returnSize)
{
    int val1=0,val2=0;
    int num1=0,num2=0;

    int i=0;
    for(i=0;i<numsSize;i++)
    {
        if(num1==0&&nums[i]!=val2)
        {
            val1=nums[i];
            num1=1;
        }
        else if(num2==0&&nums[i]!=val1)
        {
            val2=nums[i];
            num2=1;
        }
        else if(nums[i]==val1)
        {
            num1++;
        }
        else if(nums[i]==val2)
        {
            num2++;
        }
        else 
        {
            num1--;
            num2--;
        }
    }

    int* arr=(int*)malloc(8);//开辟空间
    if(arr==NULL)
    {
        return -1;
    }

    if(val1==val2)//二者相等返回其一即可
    {
        arr[0]=val1;
        *returnSize=1;
        return arr;
    }
    int count1=0,count2=0;//统计次数
    for(i=0;i<numsSize;i++)
    {
        if(nums[i]==val1)
        {
            count1++;
        }
        if(nums[i]==val2)
        {
            count2++;
        }
    }


    int flag=0;
    int x=0;
    if(count1>numsSize/3)
    {
        arr[x]=val1;
        x++;
        flag++;
    }
    if(count2>numsSize/3)
    {
        arr[x]=val2;
        x++;
        flag++;
    }
    *returnSize=flag;
    return arr;
}

N分之一

下面我们进行一般性的简易梳理。

三分之一及其以上的问题就具有了一定的一般性，随着N越来越大，代码也越来越冗杂。

将N-1种元素设为val1、val2、val3...，每个val各不相同，分别设置对应的num存储出现次数，对每个val赋值时注意不能与其他val相同，讨论特殊情况时，若遇相同，返回其一即可，详细请看代码：

int* majorityElement(int* nums, int numsSize, int* returnSize)
{
    int val1=0,val2=0;//N-1个
    int num1=0,num2=0;

    int i=0;
    for(i=0;i<numsSize;i++)
    {
        if(num1==0&&nums[i]!=val2)
        {
            val1=nums[i];
            num1=1;
        }
        else if(num2==0&&nums[i]!=val1)
        {
            val2=nums[i];
            num2=1;
        }
        else if(nums[i]==val1)
        {
            num1++;
        }
        else if(nums[i]==val2)
        {
            num2++;
        }
        else 
        {
            num1--;
            num2--;
        }
    }

    int* arr=(int*)malloc(8);//开辟空间
    if(arr==NULL)
    {
        return -1;
    }

    if(val1==val2)//每两个相等返回其一
    {
        arr[0]=val1;
        *returnSize=1;
        return arr;
    }
    int count1=0,count2=0;//统计次数
    for(i=0;i<numsSize;i++)
    {
        if(nums[i]==val1)
        {
            count1++;
        }
        if(nums[i]==val2)
        {
            count2++;
        }
    }


    int flag=0;
    int x=0;
    if(count1>numsSize/3)
    {
        arr[x]=val1;
        x++;
        flag++;
    }
    if(count2>numsSize/3)
    {
        arr[x]=val2;
        x++;
        flag++;
    }
    *returnSize=flag;
    return arr;
}

感谢你的阅读与耐心~