java – 查找列表中所需条目的数量？

发布时间：2020-12-15 02:35:20 所属栏目：Java 来源：网络整理

导读：设计一种算法,给定数组中n个元素的列表,找到列表中出现超过n / 3次的所有元素.该算法应该在线性时间内运行(n = 0) 您应该使用比较并实现线性时间.没有散??列/过多的空间/并且不使用标准的线性时间确定性选择算法？我觉得问题是自我封锁？解决方法提示：看

设计一种算法,给定数组中n个元素的列表,找到列表中出现超过n / 3次的所有元素.该算法应该在线性时间内运行(n> = 0)

您应该使用比较并实现线性时间.没有散??列/过多的空间/并且不使用标准的线性时间确定性选择算法？
我觉得问题是自我封锁？

提示：看看 Boyer and Moore’s Linear Time Vote Algorithm

脚步：

>在0(n)时间内使用中位数算法算法求出数组的中值
>使用中位数作为枢轴元素的分区
>在每个部分之间使用摩尔的投票算法
a)中位数和第一元素和
b)中位数和最后一个元素
>检查中位数是否是必需元素.

有关解决此问题的更详细算法,请参阅this文档.真的,这会非常有帮助.

有关更多答案,请参阅this类似帖子.

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!