多数投票算法，有n个人和m个候选人，但m是已知的。
多数投票算法，有n个人和m个候选人，但m是已知的。
提问于 2016-10-20 03:26:59
这个问题很长，所以我将简短地解释一下。
问:有许多人投票选举委员会主席。每个人都可以为一个拥有唯一id的人投票(它是正整数，投票将存储在数组中)。主席将是投票最多的主席。设计算法来确定谁是椅子，时间复杂度是多少？那么，如果有m
(编辑:好的，没有boyer算法)
对于第二部分，我不知道为什么我知道m的值会产生影响。问题的最后一部分听起来似乎有更有效的方法来解决问题时，m是已知的。
回答 1
Software Engineering用户
回答已采纳
发布于 2016-10-20 05:21:33
按照您的要求，这个问题有一个简单的解决方案:为候选人创建一个计数器数组，并为每个增加该候选人计数器的选票创建一个计数器；在投票结束时，扫描列表并找到最高值。O(n)假设n >> m下的时间复杂性(这将是使这样的投票系统具有现实可行性的先决条件)，如果不能假定m是小的，则O(n + m)。O(m)储存
如果您的候选in没有按顺序分配，则解决方案会有点困难，但您可以简单地使用哈希表将这些in映射到数组中的索引。这不影响复杂性，因为哈希表具有O(1) 典型查找。
除了这个实现之外，你真正想要的唯一理由是如果你期望'm‘很大，但这将是一个非常不寻常的情况。
页面原文内容由Software Engineering提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://softwareengineering.stackexchange.com/questions/334096
复制相关文章
相似问题
腾讯云开发者
