295.数据流的中位数

        先来看中位数的定义，提取一下关键词，中位数将一组按照顺序排序好的数据，分成两部分，例如 1 2 3 4 5 6,中位数 3.5 将数据分成了[1,2,3]和[4,5,6]，想看定义的同学可以自行阅读

        中位数（Median）又称中值，统计学中的专有名词，是按顺序排列的一组数据中居于中间位置的数，代表一个样本、种群或概率分布中的一个数值，其可将数值集合划分为相等的上下两部分。对于有限的数集，可以通过把所有观察值高低排序后找出正中间的一个作为中位数。如果观察值有偶数个，通常取最中间的两个数值的平均数作为中位数。

        解法一：暴力解法

        核心思路是直接按顺序插入新元素。计算中位数时分为两种情况：当数组长度为奇数时直接返回中间元素；当长度为偶数时则取中间两个元素的平均值。该算法的时间复杂度为O(n)，每个元素的插入操作耗时O(logn)。虽然效率不高，但对于题目给定的5*10^4*10^5级别数据量仍可勉强通过。

class MedianFinder {
public:vector<double> arr;MedianFinder() {}void addNum(int num) {auto it = ranges::lower_bound(arr.begin(),arr.end(),num);arr.insert(it,num);}double findMedian() {int n = arr.size();if (n % 2 == 1) {return arr[n / 2];}else{return (arr[(n - 1) / 2] + arr[n / 2]) / 2.0;}}
};

        时间复杂度：O(n)

        空间复杂度：O(1)

       解法二：利用数据中位数将数据分成两部分的特性，我们可以采用最小堆 right 和最大堆 left 来实现。例如对于数组[1,2,3,4,5,6]，left 存储[1,2,3]，right 存储[4,5,6]，中位数即为 left 堆顶3和right 堆顶4的平均值。

在addNum操作不断插入新数据时，为了保证能快速通过堆顶元素计算中位数，需要始终遵循以下原则：

1. left中的所有元素均小于right中的元素
2. left的长度等于right的长度，或比right多1

具体维护方法如下：

• 当前left的长度等于right的长度

          插入的元素较大：新元素放入 right 中，此时 right 的长度比 left 大，需要将 right 的最小值(堆顶)放入 left ，然后 right 弹出堆顶

          插入的元素较小：新元素放入 left 中，此时 left 的长度比 right 多1，符合原则

          以上两种情况可以归结于，right 放入新元素，将 right 的堆顶放入 left ，right 弹出堆顶

• 当前 left 的长度比 right 多1

          插入的元素较大：新元素放入 right 中，此时 left 长度与 right 长度相等，符合原则

          插入的元素较小：新元素放入 left 中，此时 left 长度比 right 多 2，需要将 left 的最大值(堆顶)放入 right，left 弹出堆顶

          以上两种情况可以归结于，left 放入新元素，将 left 的堆顶放入 right ，left 弹出堆顶

最终，若 left 长度大于 right，则中位数为left堆顶；否则中位数为两个堆顶的平均值。

        代码：

class MedianFinder {
public:priority_queue<int> left;priority_queue<int,vector<int>,greater<>> right; MedianFinder() {}void addNum(int num) {if (left.size() == right.size()) {right.emplace(num);left.emplace(right.top());right.pop();}else{left.emplace(num);right.emplace(left.top());left.pop();}}double findMedian() {if (left.size() > right.size()) {return left.top();}else{return (left.top() + right.top()) / 2.0;}}
};/*** Your MedianFinder object will be instantiated and called as such:* MedianFinder* obj = new MedianFinder();* obj->addNum(num);* double param_2 = obj->findMedian();*/

        时间复杂度：O(logn)

        空间复杂度：O(1)