[H数据结构] lc295. 数据流的中位数(对顶堆+技巧+思维+代码实现)

文章目录

- 1. 题目来源
- 2. 题目解析

1. 题目来源

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

2. 题目解析

十分经典的问题了。算法常用，剑指 offer 中也会出现，这个数据结构设计的十分巧妙！

思路：

中位数，实际上就是将数组分成有序的两段，L、R。当 L == R 时就是两端相邻点的平均值，当 L = R +1 时，就是 L 中多出来的那个数。
如果需要动态维护的话，一般思路：
- 将 L 设置成大顶堆，L 中实际上存的是数组中较小的一部分数，而堆顶是这较小数的最大值，方便向 R 去移动。
- 将 R 设置成小顶堆，R 中实际上存的是数组中较大的一部分数，而堆顶是这较大数的最小值，方便向 L 去移动。
- 设定：L.size() >= R.size() + 1，我们设置 L 的元素个数至多比 R 多一个。在这个设置下，中位数就可以从两个堆顶元素求得了。
当 num 进入时，如果：
- L.size() == R.size()，加入后，应当变成 L.size() = R.size() + 1，那么我们希望从将 R 中最小的一个加入到 L 中，所以 num 先进入 R，然后再将 R 堆顶元素加入 L，最后将 R 堆顶元素弹出。这样子做，不需要考虑 num 与 L、R 堆顶元素的大小关系。
- L.size() != R.size()，说明 L.size() = R.size() +1，加入后，应当变成 L.size() == R.size() 才对，那么我们希望将 L 中最大的一个加入到 R 中去，所以 num 先进入 L 进行比较，然后再将 L 的堆顶元素加入 R，最后将 L 堆顶元素弹出，这样子做，也不需要考虑 num 与 L、R 堆顶元素的大小关系。
获取中位数时，两个情况：
- L.size() == R.size() 那么取 L、R 堆顶元素的平均值即可。
- L.size() != R.size() 基于我们之前的设定，现在应该是 L.size() == R.size() + 1，那么直接返回 L 的堆顶元素即为中位数。

这个思路很是巧妙，可以自行画图理解下~

学习一下这个代码实现，避免情况判断。但是在效率上可能较低，如果明确了 num 和堆顶的关系，可能我们直接进行 push 一次就行了，但实际在这里一直都是 push 两次 pop 一次。

eg：

其实这里设定 L.size() >= R.size() +1 是很灵活的一个人为设定，同理我们设置 R.size() >= L.size()+1 也行，主要是为了维护左右两端的一个平衡而已。可以类比下 AVL 树。

时间复杂度： $O (n l o g n)$
空间复杂度： $O (n)$

class MedianFinder {
public:
    priority_queue<int, vector<int>, less<int>> L;
    priority_queue<int, vector<int>, greater<int>> R;
    MedianFinder() {

    }
    
    void addNum(int num) {
        if (L.size() != R.size()) {
            L.push(num);
            R.push(L.top());
            L.pop();
        } else {
            R.push(num);
            L.push(R.top());
            R.pop();
        }
    }
    
    double findMedian() {
        return L.size() == R.size() ? (L.top() + R.top()) / 2.0 : L.top();
    }
};

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