LeetCode 295. Find Median from Data Stream （堆）
LeetCode 295. Find Median from Data Stream （堆）
ShenduCC
发布于 2020-05-27 10:18:15
发布于 2020-05-27 10:18:15
求一个数组的中位数，但是这个数组是动态增加的，怎么做呢？可以考虑到用插入排序，每增加一个值，都插入排序一下，最坏的效率是O(n)，查询效率是O(1) 效率太低，会超时。更高明的做法，是维护两个堆，一个是大堆，一个是小堆，大堆的数字都大于小堆里的数字，两个堆的数字均分这个数字。大堆用最小堆实现，小堆用最大堆实现。 当插入一个数，我们把它跟大堆的堆顶，也就大数字里的最小数对比，要是比它大，就入大堆，要是比它小，就入小堆，之后再调整两个堆，保证平均，调整只要比较堆顶的数字即可。
插入效率变成O(logn),查询还是O(1)
class MedianFinder {
public:
/** initialize your data structure here. */
multiset<int> m1;
multiset<int> m2;
int n=0;
int len1;
int len2;
MedianFinder() {
m1.clear();
m2.clear();
len1=0;
len2=0;
}
void addNum(int num) {
if(len1==0&&len2==0)
{
m1.insert(num);
len1++;
n++;
return;
}
multiset<int>::iterator it = prev(m1.end());
if(num < *it)
{
m1.insert(num);
len1++;
}
else
{
m2.insert(num);
len2++;
}
if(len1<len2-1)
{
m1.insert(*m2.begin());
len1++;
m2.erase(m2.begin());
len2--;
}
if(len1-1>len2)
{
m2.insert(*prev(m1.end()));
len2++;
m1.erase(prev(m1.end()));
len1--;
}
n++;
}
double findMedian() {
if(n&1)
{
if(len1<len2)
return *m2.begin();
else
return *prev(m1.end());
}
else
return 1.0*(*prev(m1.end())+*m2.begin())/2;
}
};
/**
* Your MedianFinder object will be instantiated and called as such:
* MedianFinder* obj = new MedianFinder();
* obj->addNum(num);
* double param_2 = obj->findMedian();
*/本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2020-05-26 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读