【LeetCode热题100】【堆】数据流的中位数

题目链接：295. 数据流的中位数 - 力扣（LeetCode）

不停插入元素要求找到每个状态的中位数，用两个堆，把中位数左边的数记为left，右边的数记为right，一个大顶堆记录小于等于中位数的left，一个小顶堆记录大于中位数的right，数组长度为奇数时大顶堆比小顶堆多一个中位数，数组长度为偶数时，中位数就是两个堆顶的平均值

插入元素时，如果两个堆长度一样，先入小顶堆，这样小顶堆堆顶就是right里面最小的，弹出来放到left里面，此时left比right多一个数，并且left堆顶就是中位数，因为它比right都小，比left都大

如果left堆比right堆多一个数，那么先入left，那么left堆顶是left里面最大的数，弹出来送到right里面去，这样left和right数目相同，并且left堆顶元素小于right，right堆顶元素大于left，两个平均值就是中位数

注意优先队列默认是大顶堆

代码语言：javascript复制

class MedianFinder {
public:
    priority_queue<int> left;
    priority_queue<int, vector<int>, greater<int> > right;

    MedianFinder() {
    }

    void addNum(int num) {
        if (left.size() == right.size()) {
            right.push(num);
            left.push(right.top());
            right.pop();
        } else {
            left.push(num);
            right.push(left.top());
            left.pop();
        }
    }

    double findMedian() {
        return left.size() == right.size() ? (left.top()   right.top()) / 2.0 : left.top();
    }
};

队列 数组 数据流 int leetcode

0 人点赞