[OJ] Data Stream Median (Hard)

LintCode 81. Data Stream Median (Hard)

思路:

1. 用一個大根堆保存較小的一半數, 一個小根堆保存較大的一半數.
2. 每次根據num和兩個堆頂的數據決定往哪個堆里面放.
3. 放完后進行平衡確保兩個堆的size差不超過1.
4. 利用兩個堆的size和堆頂值計算median.

大根堆可以表示為priority_queue<int, vector<int>, less<int>>, 其實priority_queue<int>默認就是大根堆.
小根堆可以表示為priority_queue<int, vector<int>, greater<int>>.

class Solution {
public:vector<int> medianII(vector<int> &nums) {priority_queue<int, vector<int>, less<int>> sm;priority_queue<int, vector<int>, greater<int>> gt;vector<int> v;for (int n : nums) {if (gt.empty() || n > gt.top()) {gt.push(n);} else {sm.push(n);}if (sm.size() > gt.size() + 1) {int val = sm.top();sm.pop();gt.push(val);}if (gt.size() > sm.size() + 1) {int val = gt.top();gt.pop();sm.push(val);}if (gt.size() > sm.size()) {v.push_back(gt.top());} else {v.push_back(sm.top());}}return v;}
};

LeetCode 295. Find Median from Data Stream (Hard)

class MedianFinder {
private:priority_queue<int, vector<int>, less<int>> sm;priority_queue<int, vector<int>, greater<int>> gt;
public:// Adds a number into the data structure.void addNum(int num) {if (gt.empty() || num > gt.top()) {gt.push(num);} else {sm.push(num);}}// Returns the median of current data streamdouble findMedian() {while (sm.size() > gt.size() + 1) {int val = sm.top();sm.pop();gt.push(val);}while (gt.size() > sm.size() + 1) {int val = gt.top();gt.pop();sm.push(val);}if (gt.size() > sm.size()) {return gt.top();} else if (sm.size() > gt.size()) {return sm.top();} else {return (gt.top() + sm.top()) / 2.0;}}
};

時間復雜度: O(nlogn)
空間復雜度: O(n)