【map】【滑动窗口】【优先队列】LeetCode480滑动窗口中位数

news/2024/5/20 10:10:22 标签: 算法, leetcode, c++, map, 滑动窗口, 优先队列, 中位数

作者推荐

动态规划 多源路径 字典树 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_26">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++ 实现。


http://www.niftyadmin.cn/n/5290738.html

相关文章

java SSM小说阅读网站系统myeclipse开发mysql数据库springMVC模式java编程计算机网页设计

java SSM小说阅读网站系统myeclipse开发mysql数据库springMVC模式java编程计算机网页设计

一、源码特点 java SSM小说阅读网站系统是一套完善的web设计系统&#xff08;系统采用SSM框架进行设计开发&#xff0c;springspringMVCmybatis&#xff09;&#xff0c;对理解JSP java编程开发语言有帮助&#xff0c;系统具有完整的源代 码和数据库&#xff0c;系统主要采…
阅读更多...
k8s的二进制部署（源码包部署）

k8s的二进制部署（源码包部署）

实验条件&#xff1a; 主机名 IP地址 组件 作用 master01 20.0.0.17 kube-apiserver、kube-controller-manager、kube-scheduler、etcd k8s部署 master02 20.0.0.27 kube-apiserver、kube-controller-manager、kube-scheduler node01 20.0.0.37 kubelet、kube-pro…
阅读更多...
腾讯云轻量应用服务器配置(详细版)

腾讯云轻量应用服务器配置(详细版)

腾讯云轻量应用服务器价格2核2G配置3M带宽62元一年、2核4G5M配置218元一年、2核2G4M带宽118元/年。腾讯云百科txybk.com来详细说下腾讯云服务器从购买、配置到网站上线全流程&#xff0c;包括轻量服务器配置选择、应用镜像选择、重置密码、防火墙开放端口教程等详细教程&#x…
阅读更多...
llama大模型部署

llama大模型部署

看模型加载的参数设置. import torch# 初始化Half Tensor h torch.tensor([1.0,2.0,3.0], dtypetorch.half) # h torch.tensor([1.0,2.0,3.0], dtypetorch.float16) # 跟上面一行一样.# 查看数据类型 print(h.dtype) import accelerate import bitsandbytes from transformer…
阅读更多...
C# 时间获取

C# 时间获取

获取时间用来做log或文件名&#xff01; DateTime dt ; dt DateTime.Now; string timeStr dt.Hour.ToString("D2") ":" dt.Minute.ToString("D2"); 1:时间格式转换 System.DateTime currentTimenew System.DateTime(); 1.1 取当前年月日…
阅读更多...
LeetCode-移除元素（27） 合并两个有序数组（88）

LeetCode-移除元素（27） 合并两个有序数组（88）

1.移除元素&#xff08;27&#xff09; 题目描述&#xff1a; 给你一个数组 nums 和一个值 val&#xff0c;你需要 原地 移除所有数值等于 val 的元素&#xff0c;并返回移除后数组的新长度。 不要使用额外的数组空间&#xff0c;你必须仅使用 O(1) 额外空间并 原地 修改输入…
阅读更多...
07.kubernetes客户端部署

07.kubernetes客户端部署

kubernetes 客户端部署 主要是配置 kubectl 完成以下两个操作： 首先是要实现通过命令行连接到Kubernetes的apiserver然后就是创建必要的 ClusterRoleBinding 实现 kubelet bootstrapping CSR 的自动验签kubelet bootstrapping主要涉及以下两个问题，官方文档已经给出详细的介…
阅读更多...
如何将自己的项目上传到github上，并进行项目管理

如何将自己的项目上传到github上，并进行项目管理

将项目上传到GitHub并进行项目管理是一个多步骤的过程。以下是一个简单的示例&#xff0c;指导您如何完成这一过程&#xff1a; 1. 创建GitHub账户 如果您还没有GitHub账户&#xff0c;请先在 GitHub 上注册一个。 2. 创建新仓库 登录您的GitHub账户。在GitHub主页的右上角…
阅读更多...
最新文章

Copyright @ 2022~2023