作者推荐
动态规划 多源路径 字典树 LeetCode2977:转换字符串的最小成本
本题涉及知识点
滑动窗口 map 优先队列
题目
中位数是有序序列最中间的那个数。如果序列的长度是偶数，则没有最中间的数；此时中位数是最中间的两个数的平均数。
例如：
[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++ 实现。
