国外地图搜房网站建设,装饰工程公司,wordpress主题momo,广州发际体育用品有限公司LintCode 81. Data Stream Median (Hard) 思路: 用一个大根堆保存较小的一半数, 一个小根堆保存较大的一半数.每次根据num和两个堆顶的数据决定往哪个堆里面放.放完后进行平衡确保两个堆的size差不超过1.利用两个堆的size和堆顶值计算median.大根堆可以表示为priority_queueint, vectorint, lessint, 其实priority_queueint默认就是大根堆. 小根堆可以表示为priority_queueint, vectorint, greaterint. class Solution {
public:vectorint medianII(vectorint nums) {priority_queueint, vectorint, lessint sm;priority_queueint, vectorint, greaterint gt;vectorint 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_queueint, vectorint, lessint sm;priority_queueint, vectorint, greaterint 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) 转载于:https://www.cnblogs.com/7z7chn/p/5223928.html
