【leetcode】295. 数据流的中位数

题目内容

295. 数据流的中位数

思路分析

参考资料

方法一：两个堆

此方法十分巧妙，这里直接上个来自这里的图：

其实就是利用中位数是最中间的数字的特点，将数字按大小分为个数相等的两部分（或数字较小的部分元素个数可以比数字较大的部分多1）：

bigger_nums：较大的一部分数字，它是一个堆顶为最小值的堆；
smaller_nums：较小的一部分数字，它是一个堆顶为最大值的堆。

经过这样巧妙地设计后，当元素总数为奇数时，中位数为smaller_nums的堆顶；元素总数为偶数时，中位数为bigger_nums的堆顶与smaller_nums的堆顶的平均值。

具体的做法为：

将新到的数字插入smaller_nums
将smaller_nums的堆顶元素移除，插入bigger_nums
若bigger_nums中的元素数比smaller_nums中的元素多，则进行调整，将bigger_nums的堆顶元素移除，插入smaller_nums
按照“当元素总数为奇数时，中位数为smaller_nums的堆顶；元素总数为偶数时，中位数为bigger_nums的堆顶与smaller_nums的堆顶的平均值”的策略返回中位数。

方法二：插入排序

由于需要将元素插入一个已排序的列表中，同时保证插入后的列表仍有序，因此想到了插入排序。

总的思路就是新来一个数字后就进行插入排序，最后根据数组的下标返回中位数。

在插入排序时，将插入的过程按照二分查找进行了优化，也叫二分插入排序。

方法三：multiset

multiset底层由二叉搜索树实现，且是有序的，插入操作的时间复杂度为O(logn)。

该方法与插入排序类似，也是利用O(logn)的时间复杂度来进行插入并排序，然后找出中位数。只不过multiset不支持用下标进行访问，因此需要使用指针来实时追踪中位数的位置。又因为中位数可能是由两个值计算而来的，因此需要两个指针。

在写代码时，需要按照以下情况考虑：

插入前的元素个数是0/奇数/偶数
插入的元素与两个指针当前所指的数字的大小关系

其实在本子上简单的写写画画就能清楚了。

另外使用C++的multiset::iterator时需要注意以下两点：

插入操作不会影响iterator本来指向的值
当multiset中已经有值a的情况下再插入值a，新a会插在旧a后面

关于这两个性质的测试可以见代码中main函数的测试部分。

代码

#include <vector>
#include <math.h>
#include <limits.h>
#include <string>
#include <iostream>
#include <queue>
#include <set>

using namespace std;

// 错误方法，中位数是*有序*列表里中间的数，要有序！
class MedianFinder1 {
public:
    vector<int> nums;
    /** initialize your data structure here. */
    MedianFinder1() {

    }
    
    void addNum(int num) {
      nums.push_back(num); 
    }
    
    double findMedian() {
       int n = nums.size();
       if (n % 2 != 0) { // 奇数
         return double(nums[(n-1)/2]);
       } else { // 偶数
         return double(nums[n/2-1] + nums[n/2]) / 2;
       }
    }
};

// 插入排序
// 时间复杂度O(n)：二分查找O(logn) + 插入后挪元素O(n)
// 空间复杂度O(n)，用于保存输入（咋有时只算额外空间有时算本身+额外...）
class MedianFinder2 {
public:
    vector<int> nums;
    int n;
    /** initialize your data structure here. */
    MedianFinder2() {
    }
    
    void addNum(int num) {
      n = nums.size();
      if (n == 0) {
         nums.push_back(num);
      } else {
         // 二分查找+插入 注意这里insert和lower_bound的结合使用
         nums.insert(lower_bound(nums.begin(), nums.end(), num), num);
      } 
    }
   
    double findMedian() {
      n = nums.size();
      if (n % 2 != 0) { // 奇数
         return double(nums[(n-1)/2]);
      } else { // 偶数
         return double(nums[n/2-1] + nums[n/2]) / 2;
      }
    }
};

//https://leetcode-cn.com/problems/find-median-from-data-stream/solution/feng-xian-dui-chong-dui-ding-dui-qiu-zho-a36j/
// 两个堆
// 时间复杂度O(logn)
// 空间复杂度O(n)
class MedianFinder3 {
public:
    priority_queue<int> smaller_nums;
    priority_queue<int, vector<int>, greater<int>> bigger_nums; // 注意这里的写法
    /** initialize your data structure here. */
    MedianFinder3() {

    }
    
    void addNum(int num) {
      // 先插入小堆
      smaller_nums.push(num);
      // 进行平衡
      bigger_nums.push(smaller_nums.top());
      smaller_nums.pop();

      // 大堆不能比小堆多
      if (bigger_nums.size() == smaller_nums.size() + 1) {
         smaller_nums.push(bigger_nums.top());
         bigger_nums.pop();
      }
    }
    
    double findMedian() {
      if (smaller_nums.size() > bigger_nums.size()) {
         return smaller_nums.top();
      } else {
         return float(smaller_nums.top() + bigger_nums.top()) / 2;
      }
    }
};

// multiset法
// 时间复杂度O(logn)，插入操作需要耗费O(logn)
// 空间复杂度O(n)，额外空间O(n)
class MedianFinder {
public:
    multiset<int> nums;
    multiset<int>::iterator left, right;

    /** initialize your data structure here. */
    MedianFinder() {

    }
    
    void addNum(int num) {
      int n = nums.size();
      nums.insert(num);
      

      if (n == 0) {
         left = nums.begin();
         right = nums.begin();
      } else if ((n % 2) == 1) { // 原本是奇数个数字
         // 如1  2  3
         //     ↑↑
         if (num >= *left) {
            ++right;
         } else {
            --left;
         }
      } else { // 原本是偶数个数字
         // 如1 3 5 7
         //     ↑ ↑
         if (num >= *left && num < *right) {
            ++left;
            --right;
         } else if (num < *left) {
            --right;
         } else {
            ++left;
         }
      }
    }
    
    double findMedian() {
       return float(*left + *right) / 2;
    }
};

int main() {
   // 对multiset<int>::iterator的测试
   multiset<int> test;
   test.insert(1);
   test.insert(3);
   test.insert(4);
   multiset<int>::iterator it;
   it = test.begin();
   it++; // it指向3
   test.insert(2); // 此时it指向的还是3，没有被插入的2影响
   it--; // it指向2
   test.insert(2);
   it--; // it指向1，证明插入已有值时，是向后插入的


   double median{0.0};
   MedianFinder* obj = new MedianFinder();
   vector<string> actions = {"MedianFinder","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian","addNum","findMedian"};
   vector<vector<int>> nums = {{},{6},{},{10},{},{2},{},{6},{},{5},{},{0},{},{6},{},{3},{},{1},{},{0},{},{0},{}};

   for (int i = 0; i < actions.size(); ++i) {
      if (actions[i] == "MedianFinder") {
         ;
      } else if (actions[i] == "findMedian") {
         cout << obj->findMedian() << endl;
      } else {
         obj -> addNum(nums[i][0]);
      }
   }
   int a=0;
}

收获

堆的那种方法确实很神奇
学习了一下插入排序
学习了下c++的multiset