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

1. 题目来源

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

相关博文：

• [剑指-Offer] 41. 数据流中的中位数(堆、泛型算法、顶级解法)
• 简洁的代码实现：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(nlogn)$
• 空间复杂度：$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();
 */