策划方案免费的网站,网站源码破解,贵阳做网站设计,网站建设低价网站到底便宜在哪多数元素#xff0c;链接奉上 方法 1.摩尔投票2.合理但错误的方法2.1暴力循环2.2排序求出中间元素中间元素 1.摩尔投票
先来简单的介绍摩尔投票#xff1a; 摩尔投票是一种用来解决绝对众数问题的算法。 什么是绝对众数呢#xff1f; 在一个集合中#xff0c;如果一个元素…多数元素链接奉上 方法 1.摩尔投票2.合理但错误的方法2.1暴力循环2.2排序求出中间元素中间元素 1.摩尔投票
先来简单的介绍摩尔投票 摩尔投票是一种用来解决绝对众数问题的算法。 什么是绝对众数呢 在一个集合中如果一个元素的出现次数比其他所有元素的出现次数之和还多那么就称它为这个集合的绝对众数。等价地说绝对众数的出现次数大于总元素数的一半。 思路 设置一个计数器count 利用绝对众数与非绝对众数相互对抗、抵消 首先遍历数组 遇到相同的count不同的count-- 在根据count的数值设置当前的candidate投票对象 因为绝对众数非绝对众数对抗过后剩下的那个元素一定是绝对众数 代码实现
int majorityElement(int* nums, int numsSize)
{//mooreint i0;int candidatenums[0];//设置投票对象int count1;//因为投票对象是nums[0]本身就是1票for(i1,count1;inumsSize;i)//遍历数组{if(candidatenums[i])//当投票对象与当前元素相同时countcount;else{//否则count--count--;if(count0)//当投票对象票数0重新选择对象{candidatenums[i];count1;//票数重置为1}}}return candidate;
}2.合理但错误的方法
这是题主自己经历的错误因为超出运行时间所以不可以用
但是 注意2.2中的方法会根据排序的不同方法而产生不同影响 例如 冒泡排序会时间出界但快速排序不会 2.1暴力循环
马有失蹄暴力循环也会
思路 设置计数器count0 利用外部循环变量作为数组下标 在内层也设置一个循环变量为数组下标 与每一个数组元素进行比较相同时count 当满足countnumssize/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];
}欢迎讨论哦
