algorithm - 在数组中出现超过 n/3 次的数

Question

我看过这个问题 Find the most common entry in an array

jon skeet 的回答令人震惊.. :)

现在我试图解决这个问题，找到一个在数组中出现超过 n/3 次的元素..

我很确定我们不能应用相同的方法，因为可能有 2 个这样的元素会出现超过 n/3 次并且会给出错误的计数警报..所以我们有什么办法可以调整 jon双向飞碟为此工作的答案..？

或者有什么解决方案可以在线性时间内运行吗？

Answer 1

Jan Dvorak's answer可能是最好的:

• 从两个空的候选位置和两个设置为 0 的计数器开始。
• 对于每个项目:
  • 如果等于任一候选，则增加相应的计数
  • 否则，如果有空槽(即计数为 0 的槽)，将其放入该槽并将计数设置为 1
  • 否则将两个计数器都减 1

最后，第二次遍历数组以检查候选人是否确实具有所需的计数。您链接到的问题不允许这样做，但我不知道如何避免此修改版本。如果有一个值出现超过 n/3 次，那么它将在一个槽中，但您不知道它是哪一个。

如果问题的这个修改版本保证有 两个 个值包含超过 n/3 个元素(通常，k-1 值超过 n/k) 那么我们就不需要第二遍了。但是当原始问题有 k=2 和 1 保证多数时，我们无法知道我们是否“应该”将其概括为保证 1 个这样的元素或保证 k-1。保证越强，问题越容易。