【程序员面试金典】面试题 17.20. 连续中值-Toy模板网

这篇具有很好参考价值的文章主要介绍了【程序员面试金典】面试题 17.20. 连续中值。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

题目描述

描述：随机产生数字并传递给一个方法。你能否完成这个方法，在每次产生新值时，寻找当前所有值的中间值（中位数）并保存。

中位数是有序列表中间的数。如果列表长度是偶数，中位数则是中间两个数的平均值。

例如，

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

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

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

void addNum(int num) - 从数据流中添加一个整数到数据结构中。
double findMedian() - 返回目前所有元素的中位数。
示例：

addNum(1)
addNum(2)
findMedian() -> 1.5
addNum(3) 
findMedian() -> 2

解题思路

思路：最直观的想法是，一个大根堆一个小根堆。中值指的是一个有序数组的最中间的一个数或者中间两个数的平均值，那么可以选择排序，但是排序所需要的时间复杂度太高了，所以就考虑什么方法能取到最中间的两个数呢？想象把数组分为两半部分，左半部分我们需要取到最右边的数，即可以使用一个大根堆存储，右半部分我们需要取到最左边的数，即可以使用一个小根堆存储。考虑到数组长度可能为奇数可能为偶数，所以我们默认设计当数组长度为奇数时小根堆比大根堆多存储一个数。

//默认是大根堆 大根堆是less<int>
priority_queue<int> maxpq;
//注意 小根堆是greater<int>
priority_queue<int,vector<int>,greater<int>> minpq;
MedianFinder() {
}
//假设小根堆可以比大根堆多一个
void addNum(int num) 
{
  if(minpq.empty()||num>=minpq.top())
  {
     if(maxpq.size()<minpq.size())
     {
        maxpq.push(minpq.top());
        minpq.pop();
     }
     //当两者相等时直接插入小根堆
     minpq.push(num);
  }
  //num<minpq.top()但是可能num>maxpq.top()
  else
  {
  	 //所以需要先插入再比较
     maxpq.push(num);
     if(maxpq.size()>minpq.size())  
     {
         minpq.push(maxpq.top());
         maxpq.pop();               
     }     
  }
} 
double findMedian() 
{
    return maxpq.size()==minpq.size()?(maxpq.top()+minpq.top())/2.0 :minpq.top();
}

总结：注意此处，是先插入再比较，还是先比较再插入。注意语法，less<int>是大根堆，而greater<int>是小根堆。文章来源地址https://www.toymoban.com/news/detail-514626.html

到了这里，关于【程序员面试金典】面试题 17.20. 连续中值的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！