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

文章目录

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

    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 ( n l o g n ) O(nlogn) O(nlogn)
                • 空间复杂度： O ( n ) O(n) O(n)

                  ---

                  class MedianFinder {
                  public:
                      priority_queue L;
                      priority_queue 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();
                   */