算法不需要初始狀态的數據信息?題目：如何得到一個數據流中的中位數？如果從數據流中讀出奇數個數值，那麼中位數就是所有數值排序之後位于中間的數值如果從數據流中讀出偶數個數值，那麼中位數就是所有數值排序之後中間兩個數的平均值，下面我們就來聊聊關于算法不需要初始狀态的數據信息?接下來我們就一起去了解一下吧!

算法不需要初始狀态的數據信息

題目：

如何得到一個數據流中的中位數？如果從數據流中讀出奇數個數值，那麼中位數就是所有數值排序之後位于中間的數值。如果從數據流中讀出偶數個數值，那麼中位數就是所有數值排序之後中間兩個數的平均值。

例如，

[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(); */

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!