我在网上发现了一个有趣的谷歌面试算法，需要线性时间[关闭]

于是我在网上找到了这个谷歌面试算法题。这真的很有趣，但我还没有想出一个好的解决方案。请看一下，并给我一个提示/解决方案，如果你能用 Java 编写代码那就太好了:)。

“设计一种算法，给定数组中 n 个元素的列表，找到在列表中出现超过 n/3 次的所有元素。 该算法应以线性时间运行。 (n >=0 ) 您应该使用比较并实现线性时间。没有散​​列/过多的空间/并且不使用标准线性时间确定性选择算法”

我的解决方案受到俄罗斯方块游戏的启发。 解决方案亮点（称为“Tetrise 过程”）： 使用三个键值对进行记账，其中key为元素，value为元素的个数。在主循环中，我们最多保留 3 个最新的不同元素。当所有三个键的计数均非零时，我们将减少所有键的计数并消除零计数键（如果有）。最后，可能有也可能没有一些残留元素。这些是俄罗斯方块过程的幸存者。请注意，剩余元素不能超过 3 个。如果没有留下任何内容，我们返回 null。否则，我们循环遍历原始 n 个元素，计算这些剩余元素的数量，并返回计数 > n/3 的元素。

证明提示： 为了证明上述算法的正确性，请注意，元素必须在俄罗斯方块过程中幸存下来或保留在残差中才能满足要求。为了了解原因，我们将移除操作的数量表示为 m，剩余元素的总数表示为 r。然后我们有 n = 3 * m + r。 从这里我们得到 m = 0。 如果某个元素未能在 Tetrise 过程中幸存下来，则其出现的最大次数为 m

时间复杂度 O(n)，空间复杂度 O(1)。