我在网上找到一个有趣的谷歌访谈算法需要线性时间

所以我在网上发现了这个Google采访算法问题。 这真的很有趣，我还没有找到一个好的解决方案。 请看一下，并给我一个提示/解决方案，如果你能用Java编写代码那将是很好的。

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

Answer 1

我的解决方案受到俄罗斯方块游戏的启发。 解决方案突出显示（被称为’Tetrise进程’）：使用三个键值对进行簿记，使用键元素，值元素的计数。 在主循环中，我们保留最多3个最新的不同元素。 当所有三个键的计数都不为零时，我们减少所有的计数并消除零计数键（如果有的话）。 最后，可能存在或可能不存在一些残余元素。 这些是俄罗斯方块进程的幸存者。 请注意，可以存在不超过3个残余元素。 如果什么都没有，我们返回null。 否则，我们遍历原始的n个元素，计算这些残余元素的数量并返回其计数> n / 3的元素。

certificate提示：为了certificate上述算法的正确性，请注意，对于一个元素必须在俄罗斯方块过程中存活或保留在残留物中以满足要求。 为了解原因，我们将删除操作的次数表示为m，并将剩余元素的总数r表示。 然后我们有n = 3 * m + r。 从这里我们得到m <= n / 3，因为r> = 0.如果一个元素在Tetrise过程中不存在，它可以出现的最大值是m <= n / 3。

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

Answer 2

提示：看看Boyer和Moore的线性时间投票算法

更好的提示：首先考虑解决大多数问题。 也就是说，尝试找到至少发生n/2次的元素。 算法的基本思想是，如果我们用e的所有其他元素抵消元素e每次出现，那么如果它是多数元素，则e将存在直到结束。

 findCandidate(a[], size) //Initialize index and count of majority element maj_index = 0; count = 1; for i = 1 to n–1 { if a[maj_index] == a[i] count++; else count--; if count == 0 { maj_index = i; count = 1; } } return a[maj_index] 

该算法遍历每个元素并保持a[maj_index]的计数。 如果下一个元素相同则递增计数，如果下一个元素不相同则递减计数，如果计数达到0，则将maj_index更改为当前元素并将count设置为1。

接下来，您需要检查此元素是否确实至少发生了n/2次，但这可以在一次传递中完成。