41.数据流中的中位数 (Hard)*

题目描述*

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

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

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

限制*

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

代码*

肯定不能直接排序，觉得可以维护一个有序的数组，每次都用二分查找检索插入的位置。要注意的是检索左边界的二分查找，搜索区间为 [l, r)，循环终止条件为 l < r。这样每次添加数据的时间复杂度应该是 logn + n。

主要慢的在于 vector 插入就需要 O(n)，所以我觉得这里不如就每次从后往前找插入的位置，比较的同时把大的交换到后面，这样一边下来也是 O(n)。但是超时了。。。

还可以用两个堆，各存一半数据，中位数就是堆顶元素。维护两个堆的数量至多差 1。

二分查找堆

class MedianFinder {
private:
    vector<int> nums;
public:
    /** initialize your data structure here. */
    MedianFinder() {
    }

    void addNum(int num) {
        if(nums.empty()) {
            nums.push_back(num);
        }else {
            int l = 0, r = nums.size();
            while(l < r) {
                int mid = l + (r - l) / 2;
                if(nums[mid] >= num) {
                    r = mid;
                }else {
                    l = mid + 1;
                }
            }
            nums.insert(nums.begin() + l, num);
        }
    }

    double findMedian() {
        int n = nums.size();
        if(n & 1) {
            return nums[n / 2];
        }else {
            return (nums[n / 2] + nums[n / 2 - 1]) / 2.0;
        }
    }
};

class MedianFinder {
private:
    priority_queue<int> low;
    priority_queue<int, vector<int>, greater<int>> high;
public:
    /** initialize your data structure here. */
    MedianFinder() { }

    void addNum(int num) {
        low.push(num);
        high.push(low.top());
        low.pop();
        if(low.size() < high.size()) {
            low.push(high.top());
            high.pop();
        }
    }

    double findMedian() {
        if(low.size() > high.size()) {
            return low.top() * 1.0;
        }else {
            return (low.top() + high.top()) / 2.0;
        }
    }

最后更新: July 23, 2022