摩尔投票的一般性方法

三分之一

参考题目：多数元素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;
}

int answer1 = 0;
int answer2 = 0;
int answer3 = 0;
int count1 = 0, count2 = 0, count3 = 0;

haha(int* arr)
{
	int val1=0, val2=0, val3=0;
	int num1=0, num2=0, num3=0;
	int i = 0;
	for (i = 0; i < 12; i++)
	{
		if (num1 == 0 && arr[i] != val2 && arr[i] != val3)
		{
			val1 = arr[i];
			num1 = 1;
		}
		else if (num2 == 0 && arr[i] != val1 && arr[i] != val3)
		{
			val2 = arr[i];
			num2 = 1;
		}
		else if (num3 == 0 && arr[i] != val1 && arr[i] != val2)
		{
			val3 = arr[i];
			num3 = 1;
		}
		else if (arr[i] == val1)
		{
			num1++;
		}
		else if (arr[i] == val2)
		{
			num2++;
		}
		else if (arr[i] == val3)
		{
			num3++;
		}
		else
		{
			num1--;
			num2--;
			num3--;
		}
	}
	if (val1 == val2 == val3)
	{
		answer1 = val1;
	}
	else if (val1 == val2 && val2 != val3)
	{
		answer1 = val1;
		answer2 = val3;
	}
	else if (val1 == val3 && val3 != val2)
	{
		answer1 = val1;
		answer2 = val2;
	}
	else if (val2 == val3 && val3 != val1)
	{
		answer1 = val1;
		answer2 = val2;
	}
	else
	{
		answer1 = val1;
		answer2 = val2;
		answer3 = val3;
	}
	for (i = 0; i < 12; i++) 
	{
		if (arr[i] == answer1)
		{
			count1++;
		}
		else if (arr[i] == answer2)
		{
			count2++;
		}
		else if (arr[i] == answer3)
		{
			count3++;
		}
	}

}
int main()
{
	int arr[12] = { 0,0,0,0,0,0,0,0,0,0,1,2 };
	haha(arr);
	printf("%d %d %d\n", answer1, answer2, answer3);//三个可能的答案，超过n/4就返回即可
	printf("%d %d %d", count1, count2, count3);//查看出现的次数
	return 0;
}

int answer1 = 0;
int answer2 = 0;
int answer3 = 0;
int count1 = 0, count2 = 0, count3 = 0;

haha(int* arr)
{
	int val1=0, val2=0, val3=0;//共有N-1个变量
	int num1=0, num2=0, num3=0;
	int i = 0;
	for (i = 0; i < 12; i++)
	{
		if (num1 == 0 && arr[i] != val2 && arr[i] != val3)//复杂的判断
		{
			val1 = arr[i];
			num1 = 1;
		}
		else if (num2 == 0 && arr[i] != val1 && arr[i] != val3)
		{
			val2 = arr[i];
			num2 = 1;
		}
		else if (num3 == 0 && arr[i] != val1 && arr[i] != val2)
		{
			val3 = arr[i];
			num3 = 1;
		}
		else if (arr[i] == val1)
		{
			num1++;
		}
		else if (arr[i] == val2)
		{
			num2++;
		}
		else if (arr[i] == val3)
		{
			num3++;
		}
		else
		{
			num1--;
			num2--;
			num3--;
		}
	}
	if (val1 == val2 == val3)//有相等的只返回其一
	{
		answer1 = val1;
	}
	else if (val1 == val2 && val2 != val3)
	{
		answer1 = val1;
		answer2 = val3;
	}
	else if (val1 == val3 && val3 != val2)
	{
		answer1 = val1;
		answer2 = val2;
	}
	else if (val2 == val3 && val3 != val1)
	{
		answer1 = val1;
		answer2 = val2;
	}
	else
	{
		answer1 = val1;
		answer2 = val2;
		answer3 = val3;
	}
	for (i = 0; i < 12; i++) 
	{
		if (arr[i] == answer1)
		{
			count1++;
		}
		else if (arr[i] == answer2)
		{
			count2++;
		}
		else if (arr[i] == answer3)
		{
			count3++;
		}
	}

}
int main()
{
	int arr[12] = { 0,0,0,0,0,0,0,0,0,0,1,2 };
	haha(arr);
	printf("%d %d %d\n", answer1, answer2, answer3);//三个可能的答案，超过n/4就返回即可
	printf("%d %d %d", count1, count2, count3);//查看出现的次数
	return 0;
}