题目描述
官方描述(中文)
2021/08/27
思路
用两个优先队列 queMax 和 queMin 分别记录大于中位数的数和小于等于中位数的数。当累计添加的数的数量为奇数时,queMin 中的数的数量比queMax 多一个,此时中位数为queMin 的队头。当累计添加的数的数量为偶数时,两个优先队列中的数的数量相同,此时中位数为它们的队头的平均值。
当进行数据插入时有两种情况:
- 当num<=queMin的队头时,将num插入到queMin中。插入后如果queMin中的大小比queMax大超过1个,需要将queMin的队头插入到queMax中。
- 当num>queMin的队头时,将num插入到queMax中。插入后如果queMax中的大小比queMin大,需要将queMax的队头插入到queMin中。
当进行数据查询时也有两种情况:
- 当queMax.size()等于queMin.size()时,返回两个队头的平均值。
- 当queMax.size()小于queMin.size()时,返回queMin的队头。
代码
class MedianFinder
{
public:
/** initialize your data structure here. */
MedianFinder()
{
}
void addNum(int num)
{
if (m_queMin.empty() || m_queMin.top() > num)
{
m_queMin.push(num);
if (m_queMin.size() > m_queMax.size() + 1)
{
m_queMax.push(m_queMin.top());
m_queMin.pop();
}
}
else
{
m_queMax.push(num);
if (m_queMax.size() > m_queMin.size())
{
m_queMin.push(m_queMax.top());
m_queMax.pop();
}
}
}
double findMedian()
{
if (m_queMax.size() == m_queMin.size())
{
if (m_queMax.empty())return 0.0;
return (double)(m_queMax.top() + m_queMin.top()) / 2;
}
if (m_queMin.size())
{
return m_queMin.top();
}
return 0.0;
}
private:
//大根堆
std::priority_queue<int, std::vector<int>, std::less<int>> m_queMin;
//小根堆
std::priority_queue<int, std::vector<int>, std::greater<int>> m_queMax;
};
运行结果
Q.E.D.