题目描述

官方描述(中文)
2021/08/27

思路

用两个优先队列 queMax 和 queMin 分别记录大于中位数的数和小于等于中位数的数。当累计添加的数的数量为奇数时，queMin 中的数的数量比queMax 多一个，此时中位数为queMin 的队头。当累计添加的数的数量为偶数时，两个优先队列中的数的数量相同，此时中位数为它们的队头的平均值。
当进行数据插入时有两种情况：

1. 当num<=queMin的队头时，将num插入到queMin中。插入后如果queMin中的大小比queMax大超过1个，需要将queMin的队头插入到queMax中。
2. 当num>queMin的队头时，将num插入到queMax中。插入后如果queMax中的大小比queMin大，需要将queMax的队头插入到queMin中。

当进行数据查询时也有两种情况：

1. 当queMax.size()等于queMin.size()时，返回两个队头的平均值。
2. 当queMax.size()小于queMin.size()时，返回queMin的队头。

代码

std::priority_queue简介

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.