C语言学习--摩尔投票算法

1.引入

2.摩尔投票算法

3.具体步骤

3.1抵消阶段

3.2检验过程

4.代码实现

5.总结

1.引入

今天做题看到一个解题思路真的看不懂，一艘才知道是这个算法。

int majorityElement(int* nums, int numsSize) {
int note=nums[0];
int count=1;
for(int i=1;i<numsSize;i++){
    if(nums[i]==note){
        count++;
    }
    else{
        count--;
        if(count<0){
            note=nums[i];
            count=1;
    }
}

}//of for
return note;

}

第一种方法就是遍历数组的每一个元素，统计出现的次数。O(n^2)的时间复杂度

第二种方法是排序，我们可以先对数组进行排序，然后判断中间的数是否满足条件，这种做法时间复杂度最低为O(nlogn)。

第三种做法是用哈希表记录元素出现的次数，然后遍历哈希表寻找满足条件的元素，此时时间复杂度为O(n)，空间复杂度为O(n)。

2.摩尔投票算法

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

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

3.具体步骤

3.1抵消阶段

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

3.2检验过程

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

4.代码实现

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;
		}
	}//of for
	
	//检验阶段
	int n = 0;
	for (int i = 0; i < numsSize; i++){
		if (major == nums[i]){
			n++;
		}
	}
	if (n > numsSize / 2){
		return major;
	}else{
		return -1;
	}
}