【C语言】每日一题（多数元素）

多数元素，链接奉上

1.摩尔投票

先来简单的介绍摩尔投票：

摩尔投票是一种用来解决绝对众数问题的算法。

什么是绝对众数呢？

在一个集合中，如果一个元素的出现次数比其他所有元素的出现次数之和还多，那么就称它为这个集合的绝对众数。等价地说，绝对众数的出现次数大于总元素数的一半。

思路：

设置一个计数器count
利用绝对众数与非绝对众数相互对抗、抵消，
首先遍历数组
遇到相同的count++，不同的count--
在根据count的数值设置当前的candidate（投票对象）
因为绝对众数＞非绝对众数，对抗过后剩下的那个元素一定是绝对众数

代码实现：

int majorityElement(int* nums, int numsSize)
{//mooreint i=0;int candidate=nums[0];//设置投票对象int count=1;//因为投票对象是nums[0]，本身就是1票for(i=1,count=1;i<numsSize;i++)//遍历数组{if(candidate==nums[i])//当投票对象与当前元素相同时count++count++;else{//否则count--count--;if(count<0)//当投票对象票数＜0，重新选择对象{candidate=nums[i];count=1;//票数重置为1}}}return candidate;
}

2.合理但错误的方法

这是题主自己经历的错误，因为超出运行时间，所以不可以用

但是
注意2.2中的方法会根据排序的不同方法而产生不同影响
例如：

冒泡排序会时间出界，但快速排序不会

2.1暴力循环

马有失蹄，暴力循环也会

思路：

设置计数器count=0
利用外部循环变量作为数组下标，
在内层也设置一个循环变量为数组下标，
与每一个数组元素进行比较，相同时count++ 当满足count＞numssize/2时break

代码实现：

int majorityElement(int* nums, int numsSize)
{int i = 0;for (i = 0; i < numsSize; i++){int count = 0;for (int j = 0; j < numsSize; j++){if (nums[i] == nums[j])count++;}if (count > numsSize / 2)break;}return nums[i];}

2.2排序+求出中间元素中间元素

思路：

先进行排序，之后求出nums[numsSize/2]（中间元素），因为绝对众数所占元素必定过半，故中间元素一定为绝对众数，再return中间元素

代码实现：

int majorityElement(int* nums, int numsSize)
{int i = 0;int tmp = 0;for (i = 0; i < numsSize - 1; i++){for (int j = 0; j < numsSize - 1 - i; j++){if (nums[j] > nums[j + 1]){tmp = nums[j];nums[j] = nums[j + 1];nums[j + 1] = tmp;}}}return nums[numsSize/2];
}

欢迎讨论哦