本文主要是介绍leetcode题：295. 数据流的中位数（困难），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
一、题目描述：295. 数据流的中位数（困难）
中位数是有序列表中间的数。如果列表长度是偶数，中位数则是中间两个数的平均值。
例如，
[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
进阶:如果数据流中所有整数都在 0 到 100 范围内，你将如何优化你的算法？
如果数据流中 99% 的整数都在 0 到 100 范围内，你将如何优化你的算法？来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-median-from-data-stream
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
二、解题思路
创建两个堆，一个最大堆heap_max，一个最小堆heap_min（这里使用multiset 实现）.插入的时候保证最大堆和最小堆的元素个数不超过1。当插入一个元素
1）如果最大堆的个数大于最小堆的个数，并且这个元素比最大堆堆顶元素小，此时应该往最大堆里插入元素（但是这样会导致两个堆的元素差距超过1），则将最大堆的堆顶元素移到最小堆，然后把要插入的元素加入最大堆，否则将元素之间插入到最小堆。
2）同理，如果最小堆元素比最大堆元素多，并且此时插入的元素比最小堆的堆顶元素大，则应该要插入的元素加入到把最小堆，为了保持平衡，将最小堆的最小元素迁移到最大堆，然后把要插入的元素加入到最小堆，否则直接将元素插入到最大堆。
3）如果两个两个堆元素个数相等，则将判断如果要插入的元素大于最小堆的堆顶元素则插入到最小堆，否则插入到最大堆。
取中值的时候，如果两个堆元素个数相等，则去最大堆和最小堆堆顶元素的平均值，否则取元素多的那个堆的堆顶元素。
三、代码
class MedianFinder {
public:/** initialize your data structure here. */MedianFinder() {}int count;map<int,int> save;vector<int> save_t;multiset<int> heap_min;multiset<int> heap_max;int findMid(int & num){int right = save_t.size()-1;int left = 0;while(right >= left){int mid = (right + left)/2;if(save_t[mid] == num)return mid;if(save_t[mid] > num){right = mid - 1;}else{left = mid + 1;}}return right + 1;}void addNum(int num) {if(heap_min.size() == heap_max.size()){if(heap_min.size() > 0 && *heap_min.begin() > num)heap_max.insert(num);else{heap_min.insert(num);}}else if(heap_min.size() > heap_max.size()){if(heap_min.size() > 0 && *heap_min.begin() < num){int swap_num = *heap_min.begin();heap_max.insert(swap_num);heap_min.erase(heap_min.begin()); heap_min.insert(num);}else{heap_max.insert(num);}}else{if(heap_max.size() > 0 && *heap_max.rbegin() > num){int swap_num = *heap_max.rbegin();heap_min.insert(swap_num);heap_max.erase(heap_max.find(swap_num));heap_max.insert(num);}elseheap_min.insert(num);}/*if(heap_min.size() < 20 && heap_min.size() > 16){print(heap_max);if(heap_max.size() > 0 )cout<<"heap_max="<<*heap_max.rbegin()<<endl;cout<<"heap_max_size="<<heap_max.size()<<endl;print(heap_min);if(heap_min.size() > 0 )cout<<"heap_min="<<*heap_min.begin()<<endl;cout<<"heap_min_size="<<heap_min.size()<<endl;cout<<"*****************"<<endl;}*///cout<<num<<endl;//int mid = findMid(num);//if(mid < 0)// mid = 0;//cout<<mid<<endl;//save_t.insert(save_t.begin() + mid,num);//save_t.push_back(num);//save[num]++ ;//count ++;}void print(multiset<int> & heap){cout<<"heap_size="<<heap.size()<<endl;for(auto it = heap.begin();it != heap.end();it++){cout<<*it<<",";}cout<<endl;}double findMedian() {if(heap_min.size() == heap_max.size()){//print(heap_max);//print(heap_min);//cout<<endl;return (double)(*heap_min.begin() + *heap_max.rbegin())/2;}else if(heap_min.size() > heap_max.size()){/*print(heap_max);print(heap_min);cout<<endl;*/return *heap_min.begin();}else{/*print(heap_max);print(heap_min);cout<<endl;*/return *heap_max.rbegin();}//sort(save_t.begin(),save_t.end());/*int mod = save_t.size()%2;int len = save_t.size();if(mod == 1)return save_t[len/2];elsereturn (double)(save_t[len/2-1] + save_t[len/2])/2;*/}double findMedian1() {int mid = (count+1)/2;int mod = count%2;int count_t = 0;for(auto it = save.begin(); it != save.end(); it++){if(mid - count_t > it->second){count_t += it->second;continue;}else if(mid - count_t == it->second){if(mod == 1)return it->first;else{int num_now = it->first;auto it_next = ++it;if(it_next != save.end()){return (double)(num_now + it_next->first)/2;}}}else{return double(it->first);}}return 0;}
};/*** Your MedianFinder object will be instantiated and called as such:* MedianFinder* obj = new MedianFinder();* obj->addNum(num);* double param_2 = obj->findMedian();*/
这篇关于leetcode题：295. 数据流的中位数（困难）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
