目录
力扣295. 数据流的中位数
解析代码
力扣295. 数据流的中位数
295. 数据流的中位数
难度 困难
中位数是有序整数列表中的中间值。如果列表的大小是偶数，则没有中间值，中位数是两个中间值的平均值。
- 例如
arr = [2,3,4]的中位数是3。 - 例如
arr = [2,3]的中位数是(2 + 3) / 2 = 2.5。
实现 MedianFinder 类:
-
MedianFinder()初始化MedianFinder对象。 -
void addNum(int num)将数据流中的整数num添加到数据结构中。 -
double findMedian()返回到目前为止所有元素的中位数。与实际答案相差10-5以内的答案将被接受。
示例 1：
输入 ["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"] [[], [1], [2], [], [3], []] 输出 [null, null, null, 1.5, null, 2.0] 解释 MedianFinder medianFinder = new MedianFinder(); medianFinder.addNum(1); // arr = [1] medianFinder.addNum(2); // arr = [1, 2] medianFinder.findMedian(); // 返回 1.5 ((1 + 2) / 2) medianFinder.addNum(3); // arr[1, 2, 3] medianFinder.findMedian(); // return 2.0
提示:
-10^5 <= num <= 10^5- 在调用
findMedian之前，数据结构中至少有一个元素 - 最多
5 * 10^4次调用addNum和findMedian
class MedianFinder {
public:
MedianFinder() {
}
void addNum(int num) {
}
double findMedian() {
}
};
/**
* Your MedianFinder object will be instantiated and called as such:
* MedianFinder* obj = new MedianFinder();
* obj->addNum(num);
* double param_2 = obj->findMedian();
*/解析代码
此题有三个解法，三个解法的find函数的时间复杂度都是O（1）。看看add的时间复杂度：
- 第一个解法是进来一个数，sort一下，这样add的时间复杂度是O（N*logN）。
- 第二个解法是插入排序的思想，这样add的时间复杂度是（N）。
- 第三个解法是用两个堆来维护中位数，这样add的时间复杂度是O（logN）。
第三个解法难想，但是做完这道题以后能想起来就行。这里用第三个解法：
将整个数组按照大小平分成两部分（如果不能平分，那就让较小部分的元素多⼀个）， 较小的部分称为左侧部分，较大的部分称为右侧部分：
将左侧部分放入大根堆中，然后将右侧元素放入小根堆中，这样就能在 O（1） 的时间内拿到中间的一个数或者两个数，进而求的平均数。
于是问题就变成了如何将一个一个从数据流中过来的数据，动态调整到大根堆或者小根堆中，并且保证两个堆的元素一致，或者左侧堆的元素比右侧堆的元素多一个。
为了方便叙述，将左侧的大根堆记为 left ，右侧的小根堆记为 right ，数据流中来的数据记为 x 。
其实，就是分类讨论的过程：
- 如果左右堆的数量相同， left.size() == right.size() ：
如果两个堆都是空的，直接将数据 x 放入到 left 中； 如果两个堆非空：
- 如果元素要放入左侧，也就是 x <= left.top() ：那就直接放，因为不会影响我们制定的规则；
- 如果要放入右侧可以先将 x 放入 right 中， 然后把 right 的堆顶元素放入 left 中
- 如果左右堆的数量不相同。那就是 left.size() = right.size() + 1：
这个时候我们关心的是 x 是否会放入 left 中，导致 left 变得过多：
- 如果 x 放入 right 中，也就是 x >= right.top() ，直接放。
- 反之，就是需要放入 left 中： 可以先将 x 放入 left 中，然后把 left 的堆顶元素放入 right 中。
只要每一个新来的元素按照上述规则执行，就能保证 left 中放着整个数组排序后的左半部分， right 中放着整个数组排序后的右半部分，就能在 O（1）的时间内求出平均数，且插入的时间复杂度首O（logN）。
class MedianFinder {
// 较小的部分称为左侧部分，较大的部分称为右侧部分：
// 将左侧部分放入大根堆中，然后将右侧元素放入小根堆中，
priority_queue<int> left; // ⼤根堆
priority_queue<int, vector<int>, greater<int>> right; // ⼩根堆
public:
MedianFinder() {
}
void addNum(int num) {
if(left.size() == right.size())
{
if(right.empty() || left.top() > num)
{
left.push(num);
}
else
{
right.push(num);
left.push(right.top());
right.pop();
}
}
else
{
if(left.top() > num)
{
left.push(num);
right.push(left.top());
left.pop();
}
else
{
right.push(num);
}
}
}
double findMedian() {
if(left.size() == right.size())
return (left.top() + right.top()) / 2.0;
return left.top();
}
};
/**
* Your MedianFinder object will be instantiated and called as such:
* MedianFinder* obj = new MedianFinder();
* obj->addNum(num);
* double param_2 = obj->findMedian();
*/