算法不需要初始状态的数据信息数据流中的中位数

导读题目：如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值如果从数据流中读出偶数个数值，那么中位数就是所....

题目：如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值，下面我们就来聊聊关于算法不需要初始状态的数据信息?接下来我们就一起去了解一下吧!

算法不需要初始状态的数据信息

题目：

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

例如，

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

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

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

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

2. double findMedian() - 返回目前所有元素的中位数。

示例：

输入：

["MedianFinder","addNum","addNum","findMedian","addNum","findMedian"]

[[],[1],[2],[],[3],[]]

输出：[null,null,null,1.50000,null,2.00000]

思路：

把数组分成两部分，第一部分的最大值和第二部分的最小值就是求中位数需要的元素。

可以维护两个堆：第一部分数据用大顶堆，第二部分数据用小顶堆。

遍历数组的过程中，维护这两个堆：

1. 如果当前元素比大顶堆小，则插入大顶堆；

2. 如果两个堆的大小差距查过1，则在两个堆之间迁移元素；

遍历数组完成后，从两个堆里计算中位数：

如果两个堆大小相同，中位数=两个堆的堆顶元素之和/2

如果两个堆大小不同，取个数较大的堆的堆顶元素。

代码：

class MedianFinder {public: /** initialize your data structure here. */ MedianFinder() { } void addNum(int num) { if(!lq.empty() && num <= lq.top()) lq.push(num); else sq.push(num); while(std::abs((int)(lq.size()-sq.size())) >=2) { if(lq.size() > sq.size()) { sq.push(lq.top()); lq.pop(); }else { lq.push(sq.top()); sq.pop(); } } } double findMedian() { if(lq.empty() && sq.empty()) return -999999999.0; if(lq.size() == sq.size()) { return (lq.top() sq.top()) / 2.0; }else if(lq.size() > sq.size()) { return lq.top(); }else { return sq.top(); } }private: priority_queue<int, vector<int>, std::less<int>> lq; priority_queue<int, vector<int>, std::greater<int>> sq;};/** * Your MedianFinder object will be instantiated and called as such: * MedianFinder* obj = new MedianFinder(); * obj->addNum(num); * double param_2 = obj->findMedian(); */