题解 | #数据流中的中位数#

// 数据流中位数： // 这种类型题目（求最大的K个数，最小的K个数） // 中位数其实就是最大的N/2个 // 首先想到优先队列，很适合处理这类需求

class Solution { public: void Insert(int num) { if(maxHeap.empty() && minHeap.empty()){ maxHeap.push(num); minHeap.push(num); flag = 1; } else { if(flag == 1) { if(num < maxHeap.top()) { maxHeap.pop(); maxHeap.push(num); }else{ minHeap.pop(); minHeap.push(num); } flag = 0; } else{ if(num < maxHeap.top()) { minHeap.push(maxHeap.top()); maxHeap.push(num); }else if(num > minHeap.top()){ maxHeap.push(minHeap.top()); minHeap.push(num); }else{ maxHeap.push(num); minHeap.push(num); } flag = 1; } } }

double GetMedian() { 
    double res;
    res = (maxHeap.top() + minHeap.top()) / 2;
    return res;
}

private: priority_queue<double, vector, less> maxHeap; priority_queue<double, vector, greater> minHeap; int flag; };