多数元素,链接奉上
方法
- 1.摩尔投票
- 2.合理但错误的方法
- 2.1暴力循环
- 2.2排序+求出中间元素中间元素
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];
}
欢迎讨论哦