寻找中位数
LeetCode 295. Find Median from Data Stream 设计一个数据结构，该数据结构动态维护一组数据，且支持如下操作: 1.添加元素: void addNum(int num)，将整型num添加至数据结构中。 2.返回数据的中位数: double findMedian()，返回其维护的数据的中位数。 中位数定义: 1.若数据个数为奇数，中位数是该组数排序后中间的数。[1,2,3] -> 2 2.若数据个数为偶数，中位数是该组数排序后中间的两个数字的平均值。[1,2,3,4] -> 2.5
class MedianFinder{
public:
MedianFinder(){
}
void addNum(int num){//将数据结构中添加一个整数
}中位数
double findMedian(){//返回该数据结构中维护的数据
}
};思考与分析
如何获取中位数? 存储结构使用数组，每次添加元素或查找中位数时对数组排序， 再计算结果
时间复杂度
1.若添加元素时排序，addNum复杂度O(n)，findMedian复杂度O(1) 2.若查询中位数时排序，addNum复杂度O(1)，findMedian复杂度 O(nlogn)
若添加元素或查询中位数是随机的操作，共n次操作，按上述思想，整体复 杂度最佳为O(n^2)，是否还有更好的方法？
算法设计，巧用堆的性质
动态维护一个最大堆与一个最小堆，最大堆存储一半数据，最小堆存储 一半数据，维持最大堆的堆顶比最小堆的堆顶小，即可解决该问题。
获取中位数
情况1:最大堆与最小堆元素个数相同时：
情况2:最大堆比最小堆多一个元素
情况3:最大堆比最小堆少一个元素：
void addNum(int num){//big_queue最大堆，small_queue最小堆
if(big_queue.empty()){
big_queue.push(num);
return；
}
if(big_queue.size() == small_queue.size()){
if(num < big_queue.top()){
big_queue.push(num);
}
else{
small_queue.push(num);
}
}
else if(big_queue.size() > small_queue.size()){
if(num > big_queue.top()){
small_queue.push(num);
}
else{
small_queue.push(big_queue.top());
big_queue.pop();
big_queue.push(num);
}
}
else if(big_queue.size() < small_queue.size()){
if(num < small.top()){
big_queue.push(num);
}
else{
big_queue.push(small_queue.top());
small_queue.pop;
small_queue.push(num);
}
}
}double findMedian(){
if(big_queue.size() == small_queue.size()){
return (big_queue.top() +small_queue.top()) /2;
}
else if (big_queue.size() > small_queue.size()){
return big_queue.top();
}
return small_queue.top();
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2018.03.12 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录
相关产品与服务
对象存储
对象存储（Cloud Object Storage，COS）是由腾讯云推出的无目录层次结构、无数据格式限制，可容纳海量数据且支持 HTTP/HTTPS 协议访问的分布式存储服务。腾讯云 COS 的存储桶空间无容量上限，无需分区管理，适用于 CDN 数据分发、数据万象处理或大数据计算与分析的数据湖等多种场景。