中位数是有序列表中间的数。如果列表长度是偶数,中位数则是中间两个数的平均值。
例如,
[2,3,4] 的中位数是 3
[2,3] 的中位数是 (2 + 3) / 2 = 2.5
设计一个支持以下两种操作的数据结构:
void addNum(int num) - 从数据流中添加一个整数到数据结构中。
double findMedian() - 返回目前所有元素的中位数。
示例:
addNum(1)
addNum(2)
findMedian() -> 1.5
addNum(3)
findMedian() -> 2
方法一:插入排序
class MedianFinder {
vector<int> store;
public:
void addNum(int num)
{
if (store.empty())
store.push_back(num);
else
store.insert(lower_bound(store.begin(), store.end(), num), num);
}
double findMedian()
{
int n = store.size();
return n & 1 ? store[n / 2] : (store[n / 2 - 1] + store[n / 2]) * 0.5;
}
};
时间复杂度:O(n)
空间复杂度:O(n)
方法二:两个堆
class MedianFinder {
priority_queue<int> lo;
priority_queue<int, vector<int>, greater<int>> hi;
public:
void addNum(int num)
{
lo.push(num);
hi.push(lo.top());
lo.pop();
if (lo.size() < hi.size()) {
lo.push(hi.top());
hi.pop();
}
}
double findMedian()
{
return lo.size() > hi.size() ? (double) lo.top() : (lo.top() + hi.top()) * 0.5;
}
};
时间复杂度:O(longn)
空间复杂度:O(n)
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)