所以我在网上发现了这个Google面试算法问题.这真的很有趣,我还没有想出一个很好的解决方案.请看看,给我一个提示/解决方案,如果你可以用
Java编写代码,这将是很棒的:).
“设计一个算法,给定一个数组中的n个元素的列表,在列表中找到所有出现超过n / 3次的元素.
该算法应该以线性时间运行. (n> = 0)
您将期望使用比较并实现线性时间.没有散列/过多的空间,并且不使用标准的线性时间确定性选择算法“
解决方法
我的解决方案是由俄罗斯方块游戏启发的.
解决方案亮点(被称为“Tetrise过程”)：
使用三个键值对进行记账,使用键的元素,计算元素的数量.在一个主循环中,我们至少保留3个最新的独特元素.当所有三个键的计数不为零时,我们减少所有的计数,并消除零计数密钥(如果有的话).最后,可能有也可能没有一些残留元素.这些是俄罗斯方方进程的幸存者.注意,可以有不超过3个残留元素.如果没有,我们返回null.否则,我们循环遍历原始的n个元素,对这些剩余元素的数量进行计数,并返回计数为> N / 3.
解决方案亮点(被称为“Tetrise过程”)：
使用三个键值对进行记账,使用键的元素,计算元素的数量.在一个主循环中,我们至少保留3个最新的独特元素.当所有三个键的计数不为零时,我们减少所有的计数,并消除零计数密钥(如果有的话).最后,可能有也可能没有一些残留元素.这些是俄罗斯方方进程的幸存者.注意,可以有不超过3个残留元素.如果没有,我们返回null.否则,我们循环遍历原始的n个元素,对这些剩余元素的数量进行计数,并返回计数为> N / 3.
证明提示：为了显示上述算法的正确性,请注意,元素必须在俄罗斯方块过程中生存或保留在残留物中以满足要求.要了解为什么,我们将删除操作的数量表示为m,剩余元素的总数r.然后我们有n = 3 * m r.从这里我们得到m <= n / 3,因为r> = 0.如果一个元素在Tetrise过程中没有生存,则它可以出现的最大出现是m <= n / 3. 时间复杂度O(n),空间复杂度O(1).