一. 数组
添加线性，访问常数
class MedianFinder {
public:
MedianFinder() {
n = 0;
}
void addNum(int num) {
n++;
nums.push_back(num);
int index = n - 1;
for(int i=index;i>0;i--)
if(nums[i]<nums[i-1]) swap(nums[i],nums[i-1]);
}
double findMedian() {
if(n%2==0) return (nums[n/2]+nums[n/2-1])*1.0/2;
else return nums[n/2];
}
private:
vector<int> nums;
int n;
};
二. 双优先队列（大根堆小根堆）
class MedianFinder {
public:
priority_queue<int, vector<int>, less<int>> queMin;//大根堆存储更小值
priority_queue<int, vector<int>, greater<int>> queMax;//小根堆存储更大值
MedianFinder() {}
void addNum(int num) {
if (queMin.empty() || num <= queMin.top()) {//优先放大根堆
queMin.push(num);
if (queMax.size() + 1 < queMin.size()) {//个数差距为2，进行平衡
queMax.push(queMin.top());
queMin.pop();
}
} else {
queMax.push(num);
if (queMax.size() > queMin.size()) {//进行平衡
queMin.push(queMax.top());
queMax.pop();
}
}
}
double findMedian() {
if (queMin.size() > queMax.size())//总个数为奇数
return queMin.top();//返回小根堆顶部
return (queMin.top() + queMax.top()) / 2.0;
}
};