1

任务是用以下方法在java中实现一个队列：

  1. enqueue //添加一个元素到队列
  2. dequeue //从队列中移除元素
  3. peekMedian //求中位数
  4. peekMinimum //找到最小值
  5. peakMaximum //找到最大值
  6. 大小 // 获取大小

假设所有的方法都在等频中被调用，任务是有最快的实现。

我当前的方法：维护一个排序数组，除了队列，所以入队和出队需要 O(logn) 和 peekMedian、peekMaximum、peekMinimum 都需要 O(1) 时间。

请建议一种更快的方法，假设所有方法都以相同的频率调用。

4

2 回答 2

4

好吧，你已经接近了 - 但仍然缺少一些东西，因为从排序数组中插入/删除是O(n)（因为插入元素的概率为 1/2 位于数组的前半部分，你将不得不向右移动以下所有元素，其中至少有 n/2，因此此操作的总复杂度O(n)平均为 + 最坏情况）

但是，如果您将排序的 DS 切换到跳过列表/平衡 BST - 您将获得O(logn)插入/删除和O(1)最小/最大/中值/大小（带缓存）

编辑：

您无法O(logN)在插入时变得更好（除非您减少peekMedian()to Omega(logN)），因为这将使您能够更好地排序O(NlogN)：

首先，请注意，对于您插入的每个“高”元素，中位数向右移动一个元素（在这里，高意味着 >= 当前最大值）。
所以，通过迭代地做：

while peekMedian() != MAX:
   peekMedian()
   insert(MAX)
   insert(MAX)

您可以找到排序数组的“较高”一半。
使用相同的方法insert(MIN)可以获得数组的最低一半。

假设你有o(logN)(small o notation, better than Theta(logN)insert 和 O(1) peekMedian()，那么你得到了一个更好的排序O(NlogN)，但是排序是个Omega(NlogN)问题。
=><=

这样insert()就不能再好O(logN)了，中位数还在O(1)。

量子点

EDIT2：修改插入中的中位数：

如果插入前的树大小为 2n+1（奇数），则旧中位数在索引 n+1 处，新中位数在同一索引处（n+1），因此如果在旧中位数之前添加元素 -你需要得到最后一个中位数的前一个节点——这就是新的中位数。如果它是在它之后添加的 - 什么都不做，旧的中位数也是新的中位数。

如果列表是偶数（2n 个元素），那么在插入之后，你应该增加一个索引（从 n 到 n+1），所以如果新元素是在中位数之前添加的 - 什么都不做，如果它是在旧元素之后添加的中位数，您需要将新中位数设置为旧中位数的下一个节点。

注意：这里的next和previous节点是根据key跟随的节点，index表示节点的“位置”（最小的是第一个，最大的是最后一个）。
我只解释了如何插入，同样的想法也适用于删除。

于 2013-01-16T16:39:50.557 回答
0

有一个更简单，也许更好的解决方案。（正如已经讨论过的，排序后的数组使入队和出队都是 O(n)，这不是很好。）

除了队列之外，还维护两个排序集。Java 库提供了例如 SortedSet，它们是平衡的搜索树。“低集”按排序顺序存储第一个上限 (n/2) 元素。第二个“高设置”具有最后一层（n / 2）。

注意：如果允许重复，则必须使用Google 的 TreeMultiset之类的东西，而不是常规的 Java 排序集。

要入队，只需添加到队列和正确的集合中。如有必要，通过移动一个元素来重新建立集合之间的平衡：要么将低集合中的最大元素移至上集合，要么将高集合中的最小元素移至低集合。出队需要相同的重新平衡操作。

如果 n 为奇数，则查找中位数只是查找低集合中的最大元素。如果 n 是偶数，则在低集合中找到最大元素，在高集合中找到最小值并平均它们。

使用本机 Java 排序集实现（平衡树），所有操作的这将是 O(log n)。这将非常容易编码。大约60行。

如果您为低集和高集实现自己的筛选堆，那么查找中值操作将有 O(1)，而所有其他操作将保持 O(log n)。

如果您继续为低集和高集实现自己的斐波那契堆，那么您也将拥有 O(1) 插入。

于 2013-01-17T03:23:00.513 回答