leetcode 链接：295. 数据流的中位数

题目

中位数是有序列表中间的数。如果列表长度是偶数，中位数则是中间两个数的平均值。
例如，
[2,3,4] 的中位数是 3
[2,3] 的中位数是 (2 + 3) / 2 = 2.5

设计一个支持以下两种操作的数据结构：

  • void addNum(int num) - 从数据流中添加一个整数到数据结构中。
  • double findMedian() - 返回目前所有元素的中位数。

示例：

  1. addNum(1)
  2. addNum(2)
  3. findMedian() -> 1.5
  4. addNum(3) 
  5. findMedian() -> 2

解答 & 代码

使用两个堆：

  • 大根堆：存储值较小的一半元素
  • 小根堆：存储值较大的一半元素

两个堆的大小应该保持平衡，即两个堆大小相等，or 大根堆比小根堆多一个元素

class MedianFinder {
private:
    priority_queue<int> maxHeap;                            // 大根堆，存储值较小的一半元素
    priority_queue<int, vector<int>, greater<int>> minHeap;    // 小根堆，存储值较大的一半元素
public:
    /** initialize your data structure here. */
    MedianFinder() {
    }

    void addNum(int num) {
        // 先将元素存入大根堆并调整排序
        maxHeap.push(num);    

        // 当前大根堆堆顶元素可能属于较大的那一半，因此转移到小根堆
        minHeap.push(maxHeap.top());
        maxHeap.pop();
        // 如果小根堆比大根堆更大，则将小根堆堆顶移到大根堆
        if(maxHeap.size() < minHeap.size())
        {
            maxHeap.push(minHeap.top());
            minHeap.pop();
        }
    }

    double findMedian() {
        if(maxHeap.size() > minHeap.size())
            return (double)maxHeap.top();
        else
            return (double)(maxHeap.top() + minHeap.top()) / 2;
    }
};

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder* obj = new MedianFinder();
 * obj->addNum(num);
 * double param_2 = obj->findMedian();
 */

执行结果：

执行结果：通过

执行用时：328 ms, 在所有 C++ 提交中击败了 12.03% 的用户
内存消耗：114.3 MB, 在所有 C++ 提交中击败了 5.30% 的用户