java – 一个有趣的Google采访算法,我在网上发现需要线性时间[cl
发布时间：2020-12-14 05:58:24 所属栏目：Java 来源：网络整理
导读：所以我在网上发现了这个Google面试算法问题.这真的很有趣,我还没有想出一个很好的解决方案.请看看,给我一个提示/解决方案,如果你可以用 Java编写代码,这将是很棒的:). “设计一个算法,给定一个数组中的n个元素的列表,在列表中找到所有出现超过n / 3次的元素.
|
所以我在网上发现了这个Google面试算法问题.这真的很有趣,我还没有想出一个很好的解决方案.请看看,给我一个提示/解决方案,如果你可以用
Java编写代码,这将是很棒的:).
“设计一个算法,给定一个数组中的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). （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |