Untitled
unknown
plain_text
a year ago
1.1 kB
3
Indexable
class MedianFinder { public: priority_queue<int,vector<int>,greater<int>>left; //maxheap priority_queue<int,vector<int>,less<int>>right; //minheap MedianFinder() { } void addNum(int num) { if (right.empty() || num > right.top()) { left.push(num); } else { right.push(num); } //maintain size diff of <=1 if(left.size()> right.size()+1){ right.push(left.top()); left.pop(); }else if(right.size()>left.size()+1){ left.push(right.top()); right.pop(); } } double findMedian() { double ans=0; if(left.size()==right.size()){ if(right.empty()) return 0; else{ double avg=(left.top() +right.top())/(2.0); return avg; } }else{ return right.size()>left.size() ?right.top():left.top(); } } }; /** * Your MedianFinder object will be instantiated and called as such: * MedianFinder* obj = new MedianFinder(); * obj->addNum(num); * double param_2 = obj->findMedian(); */
Editor is loading...
Leave a Comment