关于支持科学新闻
如果您喜欢这篇文章，请考虑通过以下方式支持我们屡获殊荣的新闻报道 订阅。通过购买订阅，您将帮助确保未来能够继续提供关于塑造当今世界的发现和思想的 impactful 故事。
解答： 1. 我们将锁轮视为从 0 到 999 的计数器。我们在开始时将其重置为 000。我们将最左边的轮子视为百位，从左边数第二个轮子视为十位，最右边的轮子视为个位。
拿起最上面的字形，将其放在桌子中央。将计数器设置为 1（从左到右读为 001）。然后按照以下算法进行操作
在最上面的字形之后，直到左侧纸堆结束，
拿起下一个字形 g
如果 g 与桌子中央的字形匹配，则
将 g 放在右侧纸堆
计数器加一
否则
计数器减一
如果计数器值大于 0
将 g 移动到右侧纸堆
否则如果计数器值为 0
将桌子上的纸莎草纸移动到右侧纸堆
将 g 放在桌子中央
将计数器设置为 1
结束如果
结束如果
在遍历完左侧纸堆中的所有纸莎草纸后，桌子上会有一张纸莎草纸，右侧纸堆上有 998 张。将计数器设置为 1 (001)，并计算桌子中央字形出现的次数（即纸莎草纸的数量）。如果计数器值大于等于 500，则该字形占多数。否则，没有字形占多数。
为什么这个方法有效？假设某个符号至少出现 500 次。那么在清空左侧纸堆后，它将位于桌子中央，因为它将享受 500 次递增（加一）并最多遭受 499 次递减（减一）。任何其他符号最多出现 N < 500 次，将遭受超过 N 次递减。如果没有符号占多数，那么第二次遍历将显示计数低于 500。
拓展阅读
J. Strother Moore（1981 年德克萨斯大学技术报告 32）的 technical report “快速多数投票算法” 是该算法的来源。随后出现了大量的“重击者”算法文献。在该文献中，G. Manku 和 R. Motwani 于 2002 年在 VLDB 上发表的题为 “数据流上的近似频率计数” 的论文包含了一种对第二个问题具有启发性的方法。您可以通过您喜欢的搜索引擎找到这两篇论文。