Day7-线性表-堆-寻找中位数
一 唠唠嗑
咳咳，今天是第七天了，来讲一道利用堆的，很巧，但是很简单的题
什么？你问我为什么拖更？
二 来吧！
Q：设计一个数据结构，该数据结构动态维护一组数据，且支持以下操作：
1.添加元素：void addNum（int num），将num添加进数据结构中
2.返回中位数：double findMedian（），返回其维护的中位数
中位数定义：
若数据个数为奇数，中位数是该数据排序后中间的数。
【1，2，3】，return 2
若数据个数为偶数，中位数是该数据排序后中间两个数的平均值。
【1，2，3，4】，return 2.5
三 想想呗
此时你脱口而出，这还不简单？找个数组存啊，插入一个就排序啊，排完序之后，根据数组个数找中位数呗，这种题也拿来面我，渣渣
此时的面试官狡黠一笑，哦，看起来可以，那你能不能给我一个时间复杂度为N的算法？
你：
然后面试官
好了，说正经的，显然不能这么干啊。
最好的算法是：维护一个最大堆，和最小堆
时刻保持最大堆堆顶，一直小于最小堆堆顶
且时刻保持，最大堆，与最小堆的元素个数差，<=1
这样就保持了，最大堆里存一半相对小的数，最小堆里存了一半相对大的数
取中位数的时候，根据最大堆，最小堆元素个数来判断，是取谁的堆顶元素
这样我就做到了，时间复杂度为N，即，插完，同时排完，同时取中位数为O（1）
听起来有点拗口？没关系，举个栗子就好了~
对于数组nums = 【6，10，1，7，99，4，33】
遍历进行插入我维护的“数据结构”
第一个元素，直接插最大堆
插入后最大堆【6】，最小堆【】
第二个元素，此时最大堆size（是1）> 最小堆size（是0）
即第二种情况：此时10 > 最大堆堆顶元素6，直接将10插入最小堆
插入后最大堆【6】，最小堆【10】
第三个元素，此时最大堆size（是1）= 最小堆size（是1）
即第一种情况：此时1 < 最大堆堆顶元素6，就插入最大堆
插入后最大堆【6，1】，最小堆【10】
第四个元素，此时最大堆size（是2）> 最小堆size（是1）
仍然是第二种情况：此时7 > 最大堆堆顶元素6，直接将7插入最小堆
插入后最大堆【6，1】，最小堆【7，10】
第五个元素，此时最大堆size（是2）= 最小堆size（是2）
仍然是第一种情况：此时99 > 最大堆堆顶元素6，就插入最小堆
插入后最大堆【6，1】，最小堆【7，10，99】
第六个元素，此时最大堆size（是2）< 最小堆size（是3）
即第三种情况：此时4 < 最小堆堆顶元素7，直接插入最大堆
插入后最大堆【6，1，4】，最小堆【7，10，99】
同理第七个元素，插入到最小堆。
求中位数时，逻辑简单，注释中就写的非常清晰了
需要注意的是，第二三种情况下，有逻辑，栗子中没覆盖到，大家还是动动手，体会一下为什么这样做
四 完整代码及详细注释
//
// Created by renyi on 2019-06-10.
//
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
class FindMedian{
public:
FindMedian(){//核心思想：每次插入后，最大堆堆顶，必须要小于最小堆堆顶，且插入前后，最大堆，最小堆元素个数差，要<=1
}
void addNum(int num){//因为最大堆元素整体小于最小堆，所以进来的第一个元素先插入最大堆
if (more_heap.empty()){//若最大堆元素是空，即这是插第一个元素
more_heap.push(num);//插入最大堆，然后返回，再插就走下面逻辑了
return;
}
if (more_heap.size() == less_heap.size()){//当最大堆，最小堆元素个数一样时
if (num < more_heap.top()){//当num小于最大堆堆顶时，即第一种情况
more_heap.push(num);//直接插入最大堆
} else{
less_heap.push(num);//直接插入最小堆
}
}
else if (more_heap.size() > less_heap.size()){//最大堆元素个数，大于最小堆元素个数
if (num > more_heap.top()){//对应第二种情况
less_heap.push(num);
} else{
less_heap.push(more_heap.top());
more_heap.pop();
more_heap.push(num);
}
}
else if (more_heap.size() < less_heap.size()){//对应第三种情况
if (num < less_heap.top()){
more_heap.push(num);
} else{
more_heap.push(less_heap.top());
less_heap.pop();
less_heap.push(num);
}
}
}
double findMedian(){
if (more_heap.size() == less_heap.size()){//当元素个数相同时，总数为偶数，中位数为中间两个数的平均数
return (more_heap.top() + less_heap.top()) / 2;
} else if (more_heap.size() > less_heap.size()){
return more_heap.top();//当两者元素个数不一样，必定是奇+偶，是奇
} else{//总数奇数个，取中间的即可
return less_heap.top();//那么最大堆，最小堆，谁元素更多，谁的堆顶就是中间的数了
}
}
private:
priority_queue<double> more_heap;//初始化一个最大堆
priority_queue<double, vector<double>, greater<double> > less_heap;//初始化一个最小堆
};
int main(){
FindMedian findMedian;
int nums[] = {6, 10, 1, 7, 99, 4, 33};
for (int i = 0; i < 7; ++i) {
findMedian.addNum(nums[i]);
printf("此时的中位数为:%.1f\n", findMedian.findMedian());
}
return 0;
}
运行结果
五 总结
好记性不如烂笔头，赶紧的动手实现吧
什么？你问我堆是什么？
那就请移步作者上一篇文章好了