如何做网站推广赚钱,互联网营销行业前景,长春网站建设硕成传媒,海口注册公司流程及费用作者推荐
动态规划 多源路径 字典树 LeetCode2977:转换字符串的最小成本
本文涉及的基础知识点
C算法#xff1a;滑动窗口总结 map 优先队列
题目
中位数是有序序列最中间的那个数。如果序列的长度是偶数#xff0c;则没有最中间的数#xff1b;此时中位数是最中间的两…作者推荐
动态规划 多源路径 字典树 LeetCode2977:转换字符串的最小成本
本文涉及的基础知识点
C算法滑动窗口总结 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::multisetdouble m_setMin, m_setMax;
};
class Solution {
public:vectordouble medianSlidingWindow(vectorint nums, int k) {CMulMapMedian median;int i 0;for (; i k; i){median.Add(nums[i]);}vectordouble 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()
{vectorint nums;int k;{Solution sln;nums { 1, 3, -1, -3, 5, 3, 6, 7 },k 3;auto res sln.medianSlidingWindow(nums, k);Assert(vectordouble{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;}templateclass Tvoid PopIsTopIsDel(T que, std::unordered_multisetint 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_queueint m_queTopMax;std::priority_queueint, vectorint, greaterint m_queTopMin;std::unordered_multisetint 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 C17 或者 操作系统win10 开发环境 VS2022 C17 如无特殊说明本算法用C 实现。
