C语言刷题之摩尔投票法

水深无声 2024-03-29 16:27 16阅读 0赞

**目录**

1.引入

2.摩尔投票算法

3.基本步骤

摩尔投票法分为两个阶段：

1.抵消阶段

2.检验阶段

4.代码实现

5.扩展沿伸

6.总结

--------------------

### 1.引入 ###

我们来看一个问题：

> ***假设有一个无序数组长度为n，要求找出其中出现次数超过n/2的数，要求时间复杂度为O(n),空间复杂度为O(1).***
> 
> --------------------
> 
> 第一种方法就是遍历数组的每一个元素，统计出现的次数，但时间复杂度显然不符合要求。第二种方法是排序，我们可以先对数组进行排序，然后判断中间的数是否满足条件，这种做法时间复杂度最低为O(nlogn)。
> 
> 第三种做法是用哈希表记录元素出现的次数，然后遍历哈希表寻找满足条件的元素，此时时间复杂度为O(n)，空间复杂度为O(n)。
> 
> --------------------
> 
> 显然以上三种做法都不能同时符合题目空间复杂度和时间复杂度的要求，下面我们将介绍一种主要解决多数元素的一种算法---摩尔投票算法

### 2.摩尔投票算法 ###

摩尔投票法又称多数投票法，主要用于解决一个数组中的众数(要求数量超过数组长度的二分之一)的问题。它的原理如下：

> 我们将数组的元素想象成一张张选票，数字代表候选人的序号，每次从数组中取两个元素，如果两个元素相同，则选票数进行累加；如果不相同，则选票进行抵消，直到遍历完整个数组。如果数组中存在符合要求的候选人，则最后剩下的选票一定是最终候选人的序号。(极限一换一规则)

### 3.基本步骤 ###

#### 摩尔投票法分为两个阶段： ####

#### 1.抵消阶段 ####

本阶段将数组的元素(候选人)进行抵消。我们先定义候选人major为第一个元素，然后设置计数器count为1，向后进行遍历，当后续元素和major相等，则count++，否则count--。如果count为0时，就将候选人major改为下一个元素，count置1，以此循环直到数组遍历完毕。如果数组中存在出现次数大于n/2的元素，则最后major一定是这个元素。动图如下：

![c83113de36e74ae5bf1d8c6f75976889.gif][]

#### 2.检验阶段 ####

由于我们不知道数组是否存在符合条件的多数元素，所以需要对最后的major进行检验。例如数组为【1，2，3】，最后求出的major为3，但3显然不是数组的多数元素。所以还需遍历一遍数组判断major出现次数是否大于n/2。

--------------------

### 4.代码实现 ###

回到我们文章开头的题目，这道题出处为[LeetCode第169题][LeetCode_169]，代码如下：

int majorityElement(int* nums, int numsSize)
    {
    	//抵消阶段
    	int count = 1;
    	int major = nums[0];
    	for (int i = 1; i < numsSize; i++)
    	{
    		if (count != 0)
    		{
    			if (nums[i] == major)
    			{
    				count++;
    			}
    			else
    			{
    				count--;
    			}
    		}
    		else
    		{
    			major = nums[i];
    			count = 1;
    		}
    	}
    	
    	//检验阶段
    	int n = 0;
    	for (int i = 0; i < numsSize; i++)
    	{
    		if (major == nums[i])
    		{
    			n++;
    		}
    	}
    	if (n > numsSize / 2)
    	{
    		return major;
    	}
    	else
    	{
    		return -1;
    	}
    }

### 5.扩展沿伸 ###

我们先来看题目，本题是LeetCode第229题，是多数元素的改编题：

![f7f36cdcf1a74c9090164ed19d5a7439.png][]

本题的本质还是求众数，通过题目我们可以得知，出现次数超过n/3次的元素至多只有两个。因此我们可以将摩尔投票法进行扩展，步骤如下：

> **1.**定义两个候选人，用major1和major2两个变量维护，然后设置两个计数器count1和count2，向后遍历数组。
> 
> **2.**当和major1或major2相等时，将count1或count2加1，当不等于major1和major2时将count1和count2都减1，也就是三者抵消。当count1或count2为0时则将major1或major2改为下一个候选人(数组元素)。
> 
> **3.**当遍历完数组后，再对major1和major2进行检验，即可求出答案。

代码如下：

int* majorityElement(int* nums, int numsSize, int* returnSize)
    {
    	if (nums == NULL || numsSize <= 1)    //数组为空或最多只有一个元素
    	{
    		*returnSize = numsSize;
    		return nums;
    	}
    	//抵消阶段
    	int major1 = nums[0];   //候选人1
    	int major2 = nums[1];   //候选人2
    	int count1 = 0;         //票数
    	int count2 = 0;         //票数
    	for (int i = 0; i < numsSize; i++)
    	{
    		if (nums[i] == major1)
    		{
    			count1++;
    		}
    		else if (nums[i] == major2)
    		{
    			count2++;
    		}
    		else if (count1 == 0)
    		{
    			major1 = nums[i];
    			count1 = 1;
    		}
    		else if (count2 == 0)
    		{
    			major2 = nums[i];
    			count2 = 1;
    		}
    		else
    		{
    			count1--;
    			count2--;
    		}
    	}
    
    	//检验阶段
    	int n1 = 0, n2 = 0;
    	*returnSize = 0;
    	int* ret = (int*)malloc(2 * sizeof(int));
    	for (int i = 0; i < numsSize; i++)
    	{
    		if (nums[i] == major1)
    		{
    			n1++;
    		}
    		else if (nums[i] == major2)
    		{
    			n2++;
    		}
    	}
    	if (n1 > numsSize / 3)      //major1符合要求
    	{
    		ret[*returnSize] = major1;
    		(*returnSize)++;        
    	}
    	if (n2 > numsSize / 3)     //major2符合要求
    	{
    		ret[*returnSize] = major2;
    		(*returnSize)++;
    	}
    	return ret;
    }

### 6.总结 ###

通过以上两道题目，我们了解了摩尔投票算法适用于寻找一个数组中出现次数超过一定比例的元素。

> 当题目要找出出现次数超过1/2的元素，则至多有1个元素满足
> 
> 当题目要找出出现次数超过1/3的元素，则至多有2个元素满足
> 
> 当题目要找出出现次数超过1/4的元素，则至多有3个元素满足
> 
> 当题目要找出出现次数超过1/n的元素，则至多有n-1个元素(n>=2)满足
> 
> --------------------
> 
> 至多有n个元素满足，我们就用n个变量和n个计数器来维护这n个元素。当数组遍历完后，还需再次检验这n个元素是否满足题目要求。

--------------------

***以上，就是本期全部内容。***

***制作不易，能否点个赞再走呢qwq***

[c83113de36e74ae5bf1d8c6f75976889.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/28/7f752bb85e8c4165a7081b454dc28e4c.png
[LeetCode_169]: https://leetcode.cn/problems/majority-element/
[f7f36cdcf1a74c9090164ed19d5a7439.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/28/ac23e9a916384b249a25b2def3f1c9e2.png