题意理解
不断往某个数据结构中丢数，该结构能返回中位数。如果共奇数个数，则是中间那位；偶数位数，则是中间两数的平均数 解法：
一个高效的方法是利用两个堆来处理如果将全部数据均匀分配到两个容器中，左侧容器的数据都比右侧数据小，那么中位数就和「左侧容器中的最大值，右侧容器中的最小值」密切相关，要么平均要么就是容器size较大那个容器的最值因此现在要做的就是1）让数据进容器 2）让两个容器的size尽量相近
进容器：一个数直接进某个容器是达不到目标的。必须两边都过，即从最小堆/最大堆进去，重新查到相应的最值，再把这个最值插入到另一个堆中，这样就保证了一个「全局的顺序」，即左侧容器都小于右侧容器。size相近：可以每次插入后，再看一看哪个少，再从另一个堆中取出元素放入。这样依旧保证有序性。具体实现可以是让某个堆A的size>=另一个堆Asize。最终求平均值要么是A的最值，要么是平均值
自己写的
class MedianFinder {
public:
priority_queue<int> maxheap;
priority_queue<int, vector<int>, greater<int>> minheap;
MedianFinder() {
}
void addNum(int num) {
minheap.push(num);
maxheap.push(minheap.top());
minheap.pop();
if(minheap.size()<maxheap.size()){
minheap.push(maxheap.top());
maxheap.pop();
}
}
double findMedian() {
return minheap.size()>maxheap.size()?
minheap.top():
1.0*(minheap.top()+maxheap.top())/2;
}
};
高阶玩家
默认的堆是最大堆，这时候如果插入的全是负数，取出后求绝对值，就实现了最小堆。
class MedianFinder {
priority_queue<long> small, large;
public:
void addNum(int num) {
small.push(num);
large.push(-small.top());
small.pop();
if (small.size() < large.size()) {
small.push(-large.top());
large.pop();
}
}
double findMedian() {
return small.size() > large.size()
? small.top()
: (small.top() - large.top()) / 2.0;
}
};
Processed:
0.012, SQL:
9
