剑指 Offer 41. 数据流中的中位数 数据流中第k大的数字 - lifengyu360/lifengyu_first_git_test GitHub Wiki

如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的

一、 方法一：左手一个大顶堆 + 右手一个小顶堆。

二、解题思路

我们没有必要把所有数据进行排序。只需要保证数据左半边的数都小于右半边的数，那么根据左半边的数的最大值及右半边的数的最小值即可得到中位数。 若输入的数据个数是奇数，比如 1、2、3、4、5。我们可以把左边的 1、2 存入一个大顶堆中，把右边的 3、4、5 存入一个小顶堆中。那么中位数就是小顶堆的 top()。 若输入的数据个数是偶数，比如 1、2、3、4。我们可以把左边的 1、2 存入一个大顶堆中，把右边的 3、4 存入一个小顶堆中。那么中位数就是两个堆的 top() 的和再乘 0.5。 整个过程我们需要维护两个地方：两个堆的 size() 最大只能相差 1；大顶堆的 top() 必须小于等于小顶堆的 top()。

三、实现方法 每插入一个数之前，先判断两个堆的 size() 是否相等。 若相等，先将这个数插入大顶堆，然后将大顶堆的 top() 插入小顶堆。这么做可以保证小顶堆的所有数永远大于等于大顶堆的 top()。 若不相等，先将这个数插入小顶堆，然后将小顶堆的 top() 插入大顶堆。这么做可以保证大顶堆的所有数永远小于等于小顶堆的 top()。 整个过程我们都动态地做到了平衡两个堆的 size()，即保证它们的 size() 最大只相差了 1。 结果输出 若最后两个堆的 size() 不等。由于当两个堆的 size() 相等时我们总是选择将数插入小顶堆中（先插入大顶堆但马上又将大顶堆的 top() 插入小顶堆），所以中位数一定是小顶堆的 top()。比如数据是 1、2、3、4、5，最后大顶堆中是 1、2，小顶堆中是 3、4、5，中位数是小顶堆的 top()。 若最后两个堆的 size() 相等。那么中位数就是两个堆的 top() 的和再乘 0.5。

class MedianFinder {

public:

/** initialize your data structure here. */
priority_queue<int, vector<int>, less<int> > maxheap;
priority_queue<int, vector<int>, greater<int> > minheap;

MedianFinder() {

}

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

double findMedian() {
    int maxSize = maxheap.size(), minSize = minheap.size();
    int mid1 = maxheap.top(), mid2 = minheap.top();
    return maxSize == minSize ? ((mid1 + mid2) * 0.5) : mid2;
}

//////////// //////////////////////////////////////////////////////////////////////////// // 第k个大的数字 左边大顶堆k个数字 后边不停涨就可以了

void addNumK(int num) {

    if(maxheap.size() < k) {

        maxheap.push(num);

    }
    else {
        minheap.push(num);
        minheap.push(maxheap.top());
        maxheap.pop();
        maxheap.push(minheap.top());            
    }
}

double findMedian() {

    return maxheap.top();

}

////////////////////////////===========

};

/**

  • Your MedianFinder object will be instantiated and called as such:
  • MedianFinder* obj = new MedianFinder();
  • obj->addNum(num);
  • double param_2 = obj->findMedian(); */
⚠️ **GitHub.com Fallback** ⚠️