41. 数据流中的中位数
1. 描述
如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。
例如，
[2,3,4] 的中位数是 3
[2,3] 的中位数是 (2 + 3) / 2 = 2.5
设计一个支持以下两种操作的数据结构：
- void addNum(int num) - 从数据流中添加一个整数到数据结构中。
- double findMedian() - 返回目前所有元素的中位数。
2. 例子
示例 1:
输入：
[“MedianFinder”,“addNum”,“addNum”,“findMedian”,“addNum”,“findMedian”]
[[],[1],[2],[],[3],[]]
输出：[null,null,null,1.50000,null,2.00000]
示例 2:
输入：
[“MedianFinder”,“addNum”,“findMedian”,“addNum”,“findMedian”]
[[],[2],[],[3],[]]
输出：[null,null,2.00000,null,2.50000]
3. 限制
- 最多会对 addNum、findMedian 进行 50000 次调用。
4. 题解
n 是添加到查找器中的数字个数
查找时间复杂度: O(1)
查找空间复杂度: O(1)
添加时间复杂度: O($log_2n$)
添加空间复杂度: O(n)
当数字总个数是奇数时，中位数是排序数组的正中间的那个数字；当数字总个数是偶数时，中位数是排序数组正中间两个数字的平均值，因此可以看出如果我们将排序数组的两半分别存储，则可以很方便的求出中位数。
因此我们可以考虑使用一个最大堆存放排序数组的前一半数字，而最小堆存放排序数组的后一半数字，从而可以在常数时间内求出中位数。
class MedianFinder
{
private:
priority_queue<int, vector<int>, less<int>> leftValues; // max heap, store the left half values in order
priority_queue<int, vector<int>, greater<int>> rightValues; // min heap, store the right half values in order
public:
/** initialize your data structure here. */
MedianFinder()
{
}
void addNum(int num)
{
if(leftValues.size() == rightValues.size())
{
rightValues.push(num);
leftValues.push(rightValues.top());
rightValues.pop();
}
else
{
leftValues.push(num);
rightValues.push(leftValues.top());
leftValues.pop();
}
}
double findMedian()
{
return (leftValues.size() > rightValues.size() ? leftValues.top() : (leftValues.top() + rightValues.top()) / 2.0);
}
};