LeetCode295.数据流的中位数（C++）*

思路: 1.使用数组来实现存储，但是对于数组来说，重新排列数组时间复杂度高，效率低 2.为了提高效率，需要高效率的可排列元素的容器：优先队列；使用使用两个优先队列来实现小大根堆存储前后半部分数据。根据队列尺寸来调整两队列中的元素。 原题链接： leetcode /problems/find-median-from-data-stream/description/?favorite=2ckc81c

1.题目如下：

中位数是有序整数列表中的中间值。如果列表的大小是偶数，则没有中间值，中位数是两个中间值的平均值。

例如 arr = [2,3,4] 的中位数是 3 。 例如 arr = [2,3] 的中位数是 (2 + 3) / 2 = 2.5 。 实现 MedianFinder 类:

MedianFinder() 初始化 MedianFinder 对象。

void addNum(int num) 将数据流中的整数 num 添加到数据结构中。

double findMedian() 返回到目前为止所有元素的中位数。与实际答案相差 10-5 以内的答案将被接受。

示例 1： 输入 ["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"] [[], [1], [2], [], [3], []] 输出 [null, null, null, 1.5, null, 2.0]

解释 MedianFinder medianFinder = new MedianFinder(); medianFinder.addNum(1); // arr = [1] medianFinder.addNum(2); // arr = [1, 2] medianFinder.findMedian(); // 返回 1.5 ((1 + 2) / 2) medianFinder.addNum(3); // arr[1, 2, 3] medianFinder.findMedian(); // return 2.0

提示:

-105 <= num <= 105 在调用 findMedian 之前，数据结构中至少有一个元素 最多 5 * 104 次调用 addNum 和 findMedian

2.代码如下： class MedianFinder { public: //小根堆和大根堆 priority_queue<int, vector<int>, less<int>> queMin; priority_queue<int, vector<int>, greater<int>> queMax; /* 该题的重点是如何存储属数据方便存取中位数； */ //思路一：使用有序数组来实现存储，但是对于数组来说，重新排列数组时间复杂度高，效率低 //思路二：为了提高效率，使用使用两个优先队列来实现大根堆存储数据，对数据自动排序 /* 对排序过的元素如何判断中位数；队列无法进行随机存储； 通过两个优先队列来实现，将前后半部分元素分开 */ MedianFinder() { } void addNum(int num) { // 注意判断为空条件在先 if(queMin.empty() || num<=queMin.top() ){ queMin.push(num); //维持两队列平衡，小根堆元素不能大于大根堆超过1 if(queMin.size()>queMax.size()+1){ int temp=queMin.top(); queMax.push(temp); queMin.pop(); } } else{ queMax.push(num); //设定大根堆的元素应该比小根堆小1or相等 if(queMax.size()>queMin.size()){ int temp=queMax.top(); queMin.push(temp); queMax.pop(); } } } double findMedian() { if(queMin.size()>queMax.size()){ return queMin.top(); } return (queMax.top()+queMin.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(); */