设计数据结构的题目，自由度大难度也大，看了Stefan大神的解法五体投地……果然是思维方式决定解法的简洁程度啊……Stefan大神只用了两个优先队列和一个变号操作就把这问题完美解决了……贴上代码，学习一下：
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;
}
};
网友评论