本文共 1299 字，大约阅读时间需要 4 分钟。

题目

如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。

例如，

[2,3,4] 的中位数是 3

[2,3] 的中位数是 (2 + 3) / 2 = 2.5

设计一个支持以下两种操作的数据结构：

void addNum(int num) - 从数据流中添加一个整数到数据结构中。

思路

一定是需要用到一种排序结构来存储，那今天顺便学习了一下C++中的优先队列

普通的队列是一种先进先出的数据结构，元素在队列尾追加，而从队列头删除。

在优先队列中，元素被赋予优先级。当访问元素时，具有最高优先级的元素最先删除。优先队列具有最高级先出 （first in, largest out）的行为特征。

因此构建两个优先队列，排序方式不同，称为大小堆

如果数组长度为奇数，中位数是最中间的那个，如果长度为偶数是中间偏左的那个元素

代码

class MedianFinder {public:    /** initialize your data structure here. */    //升序队列，小顶堆    priority_queue 
   
    
     ,greater
     
       > minq;    //降序队列，大顶堆    priority_queue 
      
       
        ,less
        
          > maxq; MedianFinder() { } void addNum(int num) { maxq.push(num); minq.push(maxq.top()); maxq.pop(); //不平衡的时候的操作 if(minq.size() > maxq.size()){ maxq.push(minq.top()); minq.pop(); } } double findMedian() { if(minq.size() == maxq.size()){ double a = maxq.top(); double b = minq.top(); return (a + b) / 2; } return maxq.top(); }};/** * Your MedianFinder object will be instantiated and called as such: * MedianFinder* obj = new MedianFinder(); * obj->addNum(num); * double param_2 = obj->findMedian(); */
        
       
      
     
    
   

转载地址：https://blog.csdn.net/hanmin822/article/details/105783398 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！