论文阅读：MJRTY—A Fast Majority Vote

摘要：

提出了一种新算法，用于确定任意数量的候选人中的哪一个（如果有的话）获得了选举中的多数票， 所需的比较次数最多是票数的两倍。

背景：

确定n个投票的多数票中多数票（如果有）的最佳方法是什么？ 一种显而易见的算法是一次扫描选票，对遇到的每个候选人保持连续的选票计数。 如果候选数固定，则该显而易见的算法可以按n顺序执行。 但是，如果候选人数量不固定，则运行记录的存储和检索可能会导致算法复杂度上升。

如果可以简单地对票进行排序，则可以首先对执行时间为n阶的算法进行编码，以使用Rivest-Tarjan算法找到中位数，然后检查中位数是否获得了一半以上的票。

在本文中，我们描述了一种最多需要2n次比较的算法， 该算法不要求可以对投票进行排序， 仅执行相等性比较。

实现细节：

假设有三个候选人A，B和C，并假设主席按以下顺序对代表进行投票：

（同样的票+1，不同的票-1）

A A A C C B B C C C B C C

主席拜访第三位代表后，候选人A以3票领先：

在处理接下来的三位代表时，主席将三张A票与另外三张票（C代表两票，B代表一票）配对。 在访问了第六位代表之后，k为0，第七位代表的投票使B成为领先候选人：

但是，下一位代表取消了B的短暂任职，接下来的两位代表以2票的优势将C的优势带给了C：

代码：

总结：

看到这我发现好像和我要找的不太一样，不知道能不能改成我要的算法，继续看几篇sketch试一试，多给老板制造一点学术垃圾