41. 数据流中的中位数

Posted on One min read

1. 描述

如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。
例如，
[2,3,4] 的中位数是 3
[2,3] 的中位数是 (2 + 3) / 2 = 2.5
设计一个支持以下两种操作的数据结构：

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

2. 例子

示例 1:
输入：
[“MedianFinder”,“addNum”,“addNum”,“findMedian”,“addNum”,“findMedian”]
[[],[1],[2],[],[3],[]]
输出：[null,null,null,1.50000,null,2.00000]

示例 2:
输入：
[“MedianFinder”,“addNum”,“findMedian”,“addNum”,“findMedian”]
[[],[2],[],[3],[]]
输出：[null,null,2.00000,null,2.50000]

3. 限制

  • 最多会对 addNum、findMedian 进行 50000 次调用。

4. 题解

n 是添加到查找器中的数字个数

查找时间复杂度: O(1)
查找空间复杂度: O(1)
添加时间复杂度: O($log_2n$)
添加空间复杂度: O(n)

当数字总个数是奇数时，中位数是排序数组的正中间的那个数字；当数字总个数是偶数时，中位数是排序数组正中间两个数字的平均值，因此可以看出如果我们将排序数组的两半分别存储，则可以很方便的求出中位数。

因此我们可以考虑使用一个最大堆存放排序数组的前一半数字，而最小堆存放排序数组的后一半数字，从而可以在常数时间内求出中位数。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

class MedianFinder
{
private:
    priority_queue<int, vector<int>, less<int>> leftValues; // max heap, store the left half values in order
    priority_queue<int, vector<int>, greater<int>> rightValues; // min heap, store the right half values in order
public:
    /** initialize your data structure here. */
    MedianFinder()
    {

    }

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

    double findMedian()
    {
        return (leftValues.size() > rightValues.size() ? leftValues.top() : (leftValues.top() + rightValues.top()) / 2.0);
    }
};
comments powered by Disqus