中位数 是有序整数列表中的中间值。如果列表的大小是偶数，则没有中间值，中位数是两个中间值的平均值。

例如，
[2,3,4] 的中位数是 3
[2,3] 的中位数是 (2 + 3) / 2 = 2.5
设计一个支持以下两种操作的数据结构：

void addNum(int num) - 从数据流中添加一个整数到数据结构中。

double findMedian() - 返回目前所有元素的中位数。

示例 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]

提示：

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

找中位数

初步思路是每插入一个数就进行一次排序，时间复杂度为nlogn，会超时

因为每次插入数前数组都是有序的，所以我们可以通过二分法来查找要插入到哪；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class MedianFinder {
public:
    vector<int> a;
    void addNum(int num) {
        // 使用 lower_bound 找到第一个大于或等于 num 的位置 (O(log n))
        auto it = lower_bound(a.begin(), a.end(), num);
        a.insert(it, num);
    }

    double findMedian() {
        int n = a.size();
        if (n % 2 == 0) {
            return (a[n / 2 - 1] + a[n / 2]) / 2.0;
        }
        return a[n / 2];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
void addNum(int num) {
    int l = 0, r = a.size(); // 注意：r 取 size，表示插入范围
    while (l < r) {
        int mid = l + (r - l) / 2;
        if (a[mid] < num)
            l = mid + 1;
        else
            r = mid;
    }
    // 循环结束后，l 就是 num 应该插入的索引位置
    a.insert(a.begin() + l, num);
}

进一步，因为每次插入的都是中间位置，所以我们可以把数组分两部分，左边是小的一部分，右边是大的一部分，分别用大顶堆小顶堆来维护。

每次先插入左边，然后把左边最大值给右边（就是进来一个数先两边都过一下，确保这个数在两堆大小相等前先处于正确的位置）

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
class MedianFinder {
public:
    /** initialize your data structure here. */
    MedianFinder() {}
    priority_queue<int> left;
    priority_queue<int, vector<int>, greater<int>> right;
    int n = 0;
    void addNum(int num) {
        left.push(num);
        right.push(left.top());
        left.pop();
        if (left.size() != right.size()) {
            left.push(right.top());
            right.pop();
        }
        n++;
    }

    double findMedian() {
        double l = (double)left.top();
        if (n % 2 == 0) {
            double r = (double)right.top();
            return l + (r - l) / 2.0;
        }
        return l;
    }
};