优先级队列(堆)-295.数据流的中位数-力扣(LeetCode)

个人主页：1白天的黑夜1-CSDN博客

专栏：力扣刷题录_1白天的黑夜1的博客-CSDN博客、企鹅程序员：Linux 系统与网络编程_1白天的黑夜1的博客-CSDN博客

目录

一、题目解析

1、-105 <= num <= 105

2、在调用 findMedian 之前，数据结构中至少有一个元素

3、最多 5 * 104 次调用 addNum 和 findMedian

二、算法原理

解法1：排序直接用sort

解法2：借助插入排序的思想

解法3：利用大根堆和小根堆维护数据

具体过程：

三、代码示例

解法3：

看到最后，如果对您有所帮助，还请点赞、收藏和关注一键三连，在未来还会继续带来优秀的内容，感谢观看，我们下期再见！

一、题目解析

1、-105 <= num <= 105

2、在调用 findMedian 之前，数据结构中至少有一个元素

3、最多 5 * 104 次调用 addNum 和 findMedian

二、算法原理

解法1：排序直接用sort

由于我们需要计算中位数，为了保证结果的正确性，需要在插入数据后保证数据有序，所以该解法采用对每次add操作后进行sort库函数排序

addNum操作时间复杂度为O(n * log n)

sort函数在大多数情况都是使用的快速排序，也就是我们熟知的快排

当递归深度过深时，会切换为堆排序，避免最坏情况

当数据量很少时，又会切换为插入排序

所以，无论是最好、最坏还是平均情况，sort的时间复杂度都是O(n * log n)，非常高效

findMedian操作时间复杂度为O(1)，通过下标访问或者计算即可

解法2：借助插入排序的思想

我们的本意是将插入数据后的整体有序，在解法1中我们选择的是不管三七二十一，直接将所有数据重新排序，这显然将之前有序的数据重复排序了。所以在此基础上，我们结合插入排序的思想，结合原有数据有序的性质得到了解法2

addNum的时间复杂度为O(n)

由于元素有序，对于新插入的数num，遍历有序数据，找到比他大的数，确定位置，挪动后面的数据，所以综合来看遍历数据需要O(n)挪动数据也需要O(n)，总的是2n，但仍属于O(n)这个量级的

findMedin操作时间复杂度为O(1)，同样通过下标访问或者计算即可

解法3：利用大根堆和小根堆维护数据

通过前面的解法1和解法2，我们已经明白我们的根本需求--对数据有序的维护。那么有没有什么算法或者数据结构来帮助我们进行数据的维护？解法1是sort库函数时间按复杂度是O(n * log n)，解法2是插入排序时间复杂度是O(n)，我们期待用时间复杂度为O(log n)解决数据维护。那么在我们的所学中有什么算法或数据结构是O(log n)的？它就是本文的主角堆

我们的堆排序时间复杂度是O(log n)没错，但我们该怎么用堆来处理数据呢？

当我们找中位数或者计算中位数的时候，此时的数据已经被我们分成了左右两部分，如果我们能快速找到两部分的端点值，是不是就完成了对中位数的计算。所以我们将左右部分用堆存储，左边的数用一个大根堆存储，这样top就是我们的左端点，而右边的数则用一个小根堆存储，此时的top就是我们的右端点了。由此我们完成了对数据的处理，接下来是对不同情况的具体分析

具体过程：

addNum

1、对于计算中位数的形式，对堆做出限制--保证左边的大根堆数目m要大于或等于右边小根堆数目n。为什么？当数据为偶数时，直接取两边的top计算即可；当数据为奇数时，m>n，即m的top就是中位数。所以我们在后面的维护中需要注意两个堆的个数问题。

2、当m==n

1、m==0 || num<=l.top()，我们为了维护m>n或m==n，所以num直接进入left大根堆中。

2、num>l.top()，此时num比我们左边最大的数都大，所以num要进入右边小根堆。但为了维护m>n或m==n，我们加入num到右边小根堆后，要把右边的最小值加入到左边大根堆中，使得m>n。

3、当m>n等价与m==n+1

1、num<=l.top()，此时num进入左边大根堆，并将加入后的最大值加入到右边小根堆中，维护m和n的关系

2、num>l.top()，直接进入右边小根堆，使得m和n数量相等

findMedian

1、当m==n，取出两个堆的top，除以2.0即可，因为返回的是double，如果除以2的话，会被强制类型转换导致缺失精度

2、当m>n，直接返回左边大根堆的top

三、代码示例

这里只给出解法3的代码，该兴趣的读者可以去写一写解法1和解法2，虽然会超时

解法3：

class MedianFinder {
public:
    priority_queue<int> xleft;//左边大根堆
    priority_queue<int,vector<int>,greater<int>> nright;//右边小根堆
    MedianFinder() {}
    
    void addNum(int num)
    {
        int m = xleft.size(),n = nright.size();
        if(m == n)
        {
            if(m == 0 || num<=xleft.top())
            {
                xleft.push(num);
            }
            else
            {
                nright.push(num);
                xleft.push(nright.top());
                nright.pop();
            }
        }
        else
        {
            if(num <= xleft.top())
            {
                xleft.push(num);
                nright.push(xleft.top());
                xleft.pop();
            }
            else
            {
                nright.push(num);
            }
        }
    }
    
    double findMedian()
    {
       if(xleft.size() == nright.size()) return (xleft.top()+nright.top())/2.0;
       else return xleft.top();
    }
};

看到最后，如果对您有所帮助，还请点赞、收藏和关注一键三连，在未来还会继续带来优秀的内容，感谢观看，我们下期再见！