algorithm - 数据结构问题

Question

这道题是我考试的，答不出来，想看看答案是什么(这不是作业，除了知识，对我没有任何帮助)。

我们需要创建一个数据结构来包含键为实数的元素。
数据结构应具有以下功能:
Build(S, array):用复杂度O(n)的n个元素构建数据结构S
Insert(S, k) and Delete(S, x) in O(lgn) (k是一个元素，x是数据结构中指向它的指针)
Delete-Minimal-Positive(S):删除正键最小的元素
Mode(S):在O(1)中返回在S中出现次数最多的key

现在，在 O(n) 中构建通常意味着应该使用堆，但这不允许找到频率。我找不到任何方法来做到这一点。我能想到的最好办法是构建一个红黑树 (O(nlgn))，它将用于构建频率堆。

我很想知道答案...

谢谢!

Answer 1

仅使用比较模型，这个问题没有解决方案。

Element Distinctness Problem具有可证明的 Omega(nlogn) 下界。这个(元素差异性)问题基本上是确定数组的所有元素是否不同的问题。

如果您的问题有解决方案，那么我们可以在 O(n) 时间内解决元素差异性问题(在 O(n) 时间内找到最频繁出现的元素，并查看是否有多个实例元素，再次在 O(n) 时间内)。

所以，我建议你向你的教授询问计算模型。