所以，我在网上找到这个谷歌面试算法问题。这真的很有趣，但我还没有想出一个好的解决方案呢。请看看，并给我一个提示/解决方案，这将是巨大的，如果你能写code在Java中：）

So I found this Google interview algorithm question online. It's really interesting and I still have not come up with a good solution yet. Please have a look, and give me a hint/solution, it would be great if you can write the code in Java :).

设计一个算法，给出数组中的n个元素的列表，查找所有出现次数大于N / 3次，在列表中的元素。 该算法应该以线性时间运行。 （N> = 0） 您预计将使用比较和实现线性时间。无散列/过多的空间/不使用标准的线性时间的确定性选择算法中

"Design an algorithm that, given a list of n elements in an array, finds all the elements that appear more than n/3 times in the list. The algorithm should run in linear time. (n >=0 ) You are expected to use comparisons and achieve linear time. No hashing/excessive space/ and don't use standard linear time deterministic selection algo"

推荐答案

我的解决办法的灵感来自于俄罗斯方块游戏。 解决方案亮点（被戏称为Tetrise进程的）： 使用三个键 - 值对记账，与主要元素，价值元素的数量。在主循环，我们不断最多3最新的重复元素。当所有三个键的计数不为零，我们减小所有的计数和消除零计数密钥（多个），如果有的话。在结束时，有可能会或可能不会残留一些元素。这些都是俄罗斯方块过程中的幸存者。注意，可以有不超过3残留元素。如果什么都没有留下，我们返回null。否则我们循环原n个元素，计数这些残留的元素数量，并返回那些计数> N / 3。

My solution was inspired by the Tetris game. Solution highlight (dubbed as 'Tetrise process'): use three key-value pairs for bookkeeping, with key the element, value the count of the element. In a main loop, we keep at most 3 latest distinct elements. When the count of all three keys are non-zero, we decrement the counts of all and eliminate zero-count key(s), if any. At the end, there may or may not be some residual elements. These are the survivors of the Tetris process. Note that there can be no more than 3 residual elements. If nothing left, we return null. Otherwise we loop through the original n elements, counting the number of these residual elements and return those whose count is > n/3.

证据提示： 以显示上述算法的正确性，注意，对于一个元素必须生存的方块过程或留在残余物中，以满足要求。看原因，让我们表示去除操作的次数为m和残留元素r的总数。然后我们有 N = 3 * M + R。 从这里我们得到M＆LT; = N / 3，因为R> = 0。 如果一个元素没有在Tetrise过程中不能存活，它可以出现的最大事件是M＆LT; = N / 3

Hint of proof: To show the correctness of the above algorithm, note that for an element must survive the Tetris process or remain in the residue to satisfy the requirement. To see why, let's denote the number of removal operations as m and the total count of residual elements r. Then we have n = 3 * m + r. From here we get m <= n/3, because r >= 0. If an element didn't survive the Tetrise process, the maximum occurrence it can appear is m <= n/3.

时间复杂度为O（n），空间复杂度为O（1）。

Time complexity O(n), space complexity O(1).