题目
中位数是有序序列最中间的那个数。如果序列的长度是偶数，则没有最中间的数；此时中位数是最中间的两个数的平均数。
例如：
[2,3,4]，中位数是 3
[2,3]，中位数是 (2 + 3) / 2 = 2.5
给你一个数组 nums，有一个长度为 k 的窗口从最左端滑动到最右端。窗口中有 k 个数，每次窗口向右移动 1 位。你的任务是找出每次窗口移动后得到的新窗口中元素的中位数，并输出由它们组成的数组。
示例：
给出 nums = [1,3,-1,-3,5,3,6,7]，以及 k = 3。
窗口位置 中位数
[1 3 -1] -3 5 3 6 7 1
1 [3 -1 -3] 5 3 6 7 -1
1 3 [-1 -3 5] 3 6 7 -1
1 3 -1 [-3 5 3] 6 7 3
1 3 -1 -3 [5 3 6] 7 5
1 3 -1 -3 5 [3 6 7] 6
因此，返回该滑动窗口的中位数数组 [1,-1,-1,3,5,6]。
参数：
你可以假设 k 始终有效，即：k 始终小于等于输入的非空数组的元素个数。
与真实值误差在 10 ^ -5 以内的答案将被视作正确答案。
map
map可以分成有序(单调)map和无序(哈希)map。还可分成单键map和多键map（允许重复的键）。本题用两个有序多键map。
令数据数量为n，无论n是奇数还是偶数，第二个map存放较大的n/2个数，第一个map存放余下的数。增加的时候，增加到任意一个map中，删除时那个map存在此数，就从那个map中删除。注意：如果两个map都有，则从任意一个map中删除。
需要确保两个map数量正确。如果第二个map的元素数量大于n/2，则将第二个map的数据移到第一个map；如果第二个map元素的数量小于n/2，则将第一个map的数据移动第二个map。
需要确保两个map有序 ，第一个map的元素小于等于第二个map的元素,即第一个map的最大值(*rbegin) 小于等于第二个map的最小值。如何删除rbegin ? std::prev(m_setMin.end()) 如果需要交换，说明max1 > min2 => max1不是第二个map的最小值，min2不是第一个map的最大值，所以可以先增加，再删除。
核心代码
class CMulMapMedian { public: void Add(int iNum) { m_setMax.insert(iNum); MakeValidSize(); MakeSort(); } void Del(int iNum) { if (m_setMax.count(iNum)) { m_setMax.erase(m_setMax.find(iNum)); } else { m_setMin.erase(m_setMin.find(iNum)); } MakeValidSize(); MakeSort(); } double GetMedian() { if (m_setMin.size() == m_setMax.size()) { return (*m_setMin.rbegin() + *m_setMax.begin()) / 2.0; } return *m_setMin.rbegin(); } protected: void MakeValidSize() { int iMaxSize = (m_setMin.size() + m_setMax.size()) / 2; while (m_setMax.size() < iMaxSize) { m_setMax.insert(*m_setMin.rbegin()); m_setMin.erase(std::prev(m_setMin.end())); } while (m_setMax.size() > iMaxSize) { m_setMin.insert(*m_setMax.begin()); m_setMax.erase(m_setMax.begin()); } } void MakeSort() { if (m_setMax.empty()) { return; } while (*m_setMin.rbegin() > *m_setMax.begin()) { m_setMin.insert(*m_setMax.begin()); m_setMax.insert(*m_setMin.rbegin()); m_setMin.erase(std::prev(m_setMin.end())); m_setMax.erase(m_setMax.begin()); } } std::multiset<double> m_setMin, m_setMax; }; class Solution { public: vector<double> medianSlidingWindow(vector<int>& nums, int k) { CMulMapMedian median; int i = 0; for (; i < k; i++) { median.Add(nums[i]); } vector<double> vRet; vRet.push_back(median.GetMedian()); for (; i < nums.size(); i++) { median.Add(nums[i]); median.Del(nums[i - k]); vRet.push_back(median.GetMedian()); } return vRet; } };
测试用例
int main() { vector<int> nums; int k; { Solution sln; nums = { 1, 3, -1, -3, 5, 3, 6, 7 },k = 3; auto res = sln.medianSlidingWindow(nums, k); Assert(vector<double>{1, -1, -1, 3, 5, 6}, res); } }
双优先队列（堆）+延长删除
优先队列无法删除指定元素，可以记录需要删除的元素，如果堆顶元素是需要删除的元素，则删除。
class CMedian { public: void AddNum(int iNum) { m_queTopMin.emplace(iNum); MakeNumValid(); MakeSmallBig(); } void Remove(int iNum) { if (m_queTopMax.size() && (iNum <= m_queTopMax.top())) { m_setTopMaxDel.insert(iNum); } else { m_setTopMinDel.insert(iNum); } PopIsTopIsDel(m_queTopMin, m_setTopMinDel); PopIsTopIsDel(m_queTopMax, m_setTopMaxDel); MakeNumValid(); MakeSmallBig(); } double Median() { const int iMaxNum = m_queTopMin.size() - m_setTopMinDel.size(); const int iMinNum = m_queTopMax.size() - m_setTopMaxDel.size(); if (iMaxNum > iMinNum) { return m_queTopMin.top(); } return ((double)m_queTopMin.top() + m_queTopMax.top())/2.0; } template<class T> void PopIsTopIsDel(T& que, std::unordered_multiset<int>& setTopMaxDel) { while (que.size() && (setTopMaxDel.count(que.top()))) { setTopMaxDel.erase(setTopMaxDel.find(que.top())); que.pop(); } } void MakeNumValid() { const int iMaxNum = m_queTopMin.size() - m_setTopMinDel.size(); const int iMinNum = m_queTopMax.size() - m_setTopMaxDel.size(); //确保两个队的数量 if (iMaxNum > iMinNum + 1) { int tmp = m_queTopMin.top(); m_queTopMin.pop(); m_queTopMax.emplace(tmp); PopIsTopIsDel(m_queTopMin, m_setTopMinDel); } if (iMinNum > iMaxNum) { int tmp = m_queTopMax.top(); m_queTopMax.pop(); m_queTopMin.push(tmp); PopIsTopIsDel(m_queTopMax, m_setTopMaxDel); } } void MakeSmallBig() { if (m_queTopMin.empty() || m_queTopMax.empty()) { return; } while (m_queTopMin.top() < m_queTopMax.top()) { const int iOldTopMin = m_queTopMin.top(); const int iOldTopMax = m_queTopMax.top(); m_queTopMin.pop(); m_queTopMax.pop(); m_queTopMin.emplace(iOldTopMax); m_queTopMax.emplace(iOldTopMin); PopIsTopIsDel(m_queTopMin, m_setTopMinDel); PopIsTopIsDel(m_queTopMax, m_setTopMaxDel); } } std::priority_queue<int> m_queTopMax; std::priority_queue<int, vector<int>, greater<int>> m_queTopMin; std::unordered_multiset<int> m_setTopMaxDel, m_setTopMinDel; };
class Solution { public: vector medianSlidingWindow(vector& nums, int k) { int i = 0; CMedian hlp; for (; i + 1 < k; i++) { hlp.AddNum(nums[i]); } vector vRet; for (; i < nums.size(); i++) { hlp.AddNum(nums[i]); if (i - k >= 0) { hlp.Remove(nums[i - k]); } vRet.emplace_back(hlp.Median()); } return vRet; } };
扩展阅读
视频课程
有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快
速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
相关下载
想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用C++ 实现。
