题目:
思路:
用一个大根堆装较小的数,用小根堆装较大的数,维持两个堆的大小接近。
那么取中位数时:
- large.size==small.size,(large.top+small.top)/2.0 注意2.0为了获取double
- large>small,返回large.top
- large<small,返回small.top
每次addNum时,如果small.size<large.size,那么先将large.push(num),再n=large.top,large.pop,保证取出的值是较大数中最小值,将small.push(n)。
反之亦然
class MedianFinder { public: MedianFinder() { } void addNum(int num) { if(large.size()<small.size()){ small.push(num); int n=small.top(); small.pop(); large.push(n); }else{ large.push(num); int n=large.top(); large.pop(); small.push(n); } } double findMedian() { // 如果元素不一样多,多的那个堆的堆顶元素就是中位数 if(large.size()<small.size()){ return small.top(); }else if(large.size()>small.size()){ return large.top(); }else{ return (small.top()+large.top())/2.0; } } // 小顶堆 priority_queue<int> large; // 大顶堆 priority_queue<int,vector<int>,greater<int>> small; };