数据结构查找中位数 [英] Data Structure to find median

问题描述

这是一个采访问题。设计一个类，它存储整数，并提供两个操作：

 
 void insert（int k）
 int getMedian（）
 

我想我可以使用BST，以便 insert 取O（logN）和 getMedian 取O（logN）（对于 getMedian 我应该添加每个节点的左/右子节点数） / p>

现在我想知道这是否是最有效的解决方案，没有更好的解决方案。

解决方案

您可以使用2堆，我们将会调用 Left 和 Right 。

左是一个 Max-Heap 。

正确是一个 Min-Heap 。

插入完成如下：

• 如果新元素 x 小于左然后我们插入 x 到左。


• 否则我们将 x 插入到右边。
  


• 一世f插入后 Left 从 Right 中的元素数量大于1的元素数，然后我们调用左边 c $ c>中的Extract-Max，并将其插入到右边。


• 否则插入后 Right 具有大于 Left 的元素数量的元素数，然后我们调用Extract-Min在对并将其插入左。

中位数始终是左根的根。

所以插入在 O（lg n）时间并获得中位数在 O（1）时间完成。

This is an interview question. Design a class, which stores integers and provides two operations:

void insert(int k)
int getMedian()

I guess I can use BST so that insert takes O(logN) and getMedian takes O(logN) (for getMedian I should add the number of of left/right children for each node).

Now I wonder if this is the most efficient solution and there is no better one.

解决方案

You can use 2 heaps, that we will call Left and Right.
Left is a Max-Heap.
Right is a Min-Heap.
Insertion is done like this:

• If the new element x is smaller than the root of Left then we insert x to Left.
• Else we insert x to Right.
  
• If after insertion Left has count of elements that is greater than 1 from the count of elements of Right, then we call Extract-Max on Left and insert it to Right.
• Else if after insertion Right has count of elements that is greater than the count of elements of Left, then we call Extract-Min on Right and insert it to Left.

The median is always the root of Left.

So insertion is done in O(lg n) time and getting the median is done in O(1) time.

这篇关于数据结构查找中位数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！