哪个网站推广比较好,中国推广网,asp做网站用什么写脚本,网站开发需要学习关于我#xff1a; 睡觉待开机#xff1a;个人主页 个人专栏: 《优选算法》《C语言》《CPP》 生活的理想#xff0c;就是为了理想的生活! 作者留言
PDF版免费提供#xff1a;倘若有需要#xff0c;想拿我写的博客进行学习和交流#xff0c;可以私信我将免费提供PDF版。…关于我 睡觉待开机个人主页 个人专栏: 《优选算法》《C语言》《CPP》 生活的理想就是为了理想的生活! 作者留言
PDF版免费提供倘若有需要想拿我写的博客进行学习和交流可以私信我将免费提供PDF版。 留下你的建议倘若你发现本文中的内容和配图有任何错误或改进建议请直接评论或者私信。 倡导提问与交流关于本文任何不明之处请及时评论和私信看到即回复。 参考目录 1.前言2.题目简介3.题目思路4.参考代码 1.前言
今天我们来简单分享一道不同于经典双指针啊前缀和算法…等等很有体系的题目咱们来一道不难但是思路却比较新颖的题目。 我想如果你没有接触过这类题目还真不见得可以想到这种方法——投票选举。
2.题目简介
题目链接LINK 题意题目叙述很简单给你一个数组让你找出其中出现次数超过一半的一个元素。
不知你是否想到了什么思路我立刻想到的就是用哈希数组进行一一记数然后遍历哈希数组找到出现次数超过一半的那个元素。 但是显然这种解法不满足题目要求空间复杂度是O(N)级别的我们题目要求是O(1)
这里空间复杂度的限制这样就很难了。
3.题目思路
加入数组中存在众数那么众数一定大于数组的长度的一半。 思想就是如果两个数不相等就消去这两个数最坏情况下每次消去一个众数和一个非众数那么如果存在众数最后留下的数肯定是众数。
具体做法 初始化候选人cond -1 候选人的投票次数cnt 0 遍历数组如果cnt0 表示没有候选人则选取当前数为候选人cnt 否则如果cnt 0, 表示有候选人如果当前数cond则cnt否则–cnt 直到数组遍历完毕最后检查cond是否为众数
这是什么原理呢下面我来为大家举例解读。 是这样的有很多人投票每个人都对自己心仪的对象进行投票最后的结果肯定是谁的投票高谁得第一。假设现在有一个计票员需要依次对每个人手里的票进行记录比赛结果要求很简单不用按票数排名只需要知道第一名是谁就行了对第二名第三名…并不关注。 现在我们把vector中的元素看作一个一个的投票人每个元素的数值就是对应的投票对象。而我们的计票员依次对每个人计票就是类似于我们一个变量依次遍历数组。 这时候计票员只需要准备两个变量一个变量存放当前是谁第一第二个变量是存放相比于其他人第一名的相对票数。 我们知道数组中出现次数超过一半的数字势必会比其他人所有出现次数之和都多。
4.参考代码
class Solution {
public:/*** 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可** * param numbers int整型vector * return int整型*/int MoreThanHalfNum_Solution(vectorint numbers) {// write code hereint count 0;int candidate -1;for(int i 0; i numbers.size(); i){if(count 0){candidate numbers[i];count;}else {if(numbers[i] candidate){count;}else {count--;}}}return candidate;}
};好的如果本篇文章对你有帮助不妨点个赞~谢谢。 EOF
