C++二分查找算法的应用：俄罗斯套娃信封问题

2023-11-03 08:36
文章标签 算法 c++ 问题 应用 二分 查找 套娃 信封 俄罗斯

本文主要是介绍C++二分查找算法的应用：俄罗斯套娃信封问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

本文涉及的基础知识点

二分查找

题目

给你一个二维整数数组 envelopes ，其中 envelopes[i] = [wi, hi] ，表示第 i 个信封的宽度和高度。
当另一个信封的宽度和高度都比这个信封大的时候，这个信封就可以放进另一个信封里，如同俄罗斯套娃一样。
请计算 最多能有多少个 信封能组成一组“俄罗斯套娃”信封（即可以把一个信封放到另一个信封里面）。
注意：不允许旋转信封。
示例 1：
输入：envelopes = [[5,4],[6,4],[6,7],[2,3]]
输出：3
解释：最多信封的个数为 3, 组合为: [2,3] => [5,4] => [6,7]。
示例 2：
输入：envelopes = [[1,1],[1,1],[1,1]]
输出：1
参数提示：
1 <= envelopes.length <= 105
envelopes[i].length == 2
1 <= wi, hi <= 105

超时解法

有两个地方可能超时：
一，std::map<int, int> dp = mPreYToNum;
二，for (; (ij != dp.end()) && (ij->second > len); ++ij);
一处的时间复杂度是:O(n)，最多有n个元素，所以总时间复杂度是O(n*n)，会引起超时。
二处，总时间复杂度是O(n)，最多删除n次，每个元素最多只会被删除一次。

代码

class Solution {
public:
int maxEnvelopes(vector<vector>& envelopes) {
std::map<int, vector> mXToYS;
for (const auto& v : envelopes)
{
mXToYS[v[0]].emplace_back(v[1]);
}
std::map<int, int> mPreYToNum;//y值对应最大数量，y值越大，对应的数量越大，否则被淘汰了
int iMax = 0;
for (const auto& it : mXToYS)
{
std::map<int, int> dp = mPreYToNum;
for (const auto& y : it.second)
{
int len = 0;
{//计算长度
const auto it = mPreYToNum.lower_bound(y);
len = 1 + ((mPreYToNum.begin() == it) ? 0 : std::prev(it)->second);
iMax = max(iMax, len);
}
{
const auto it = dp.lower_bound(y);
auto ij = it;
for (; (ij != dp.end()) && (ij->second > len); ++ij);
dp.erase(it, ij);
if (!dp.count(y))
{
dp[y] = len;
}
}
}
mPreYToNum.swap(dp);
}

	return iMax;
}

};

测试用例

template
void Assert(const T& t1, const T& t2)
{
assert(t1 == t2);
}

template
void Assert(const vector& v1, const vector& v2)
{
if (v1.size() != v2.size())
{
assert(false);
return;
}
for (int i = 0; i < v1.size(); i++)
{
Assert(v1[i] ,v2[i]);
}
}

int main()
{
Solution slu;
vector<vector> envelopes;
int res = 0;
envelopes = { {5,4},{6,4},{6,7},{2,3} };
res = slu.maxEnvelopes(envelopes);
Assert(res, 3);
envelopes = { {1,1},{1,1},{1,1} };
res = slu.maxEnvelopes(envelopes);
Assert(res, 1);
envelopes = { {1,1},{2,2},{2,3} };
res = slu.maxEnvelopes(envelopes);
Assert(res, 2);
envelopes = { {1,2},{2,3},{3,4},{3,5},{4,5},{5,5},{5,6},{6,7},{7,8} };
res = slu.maxEnvelopes(envelopes);
Assert(res, 7);

//CConsole::Out(res);

}

正确解法

变量含义

mXToYSkey为envelopes的x，值为envelopes的y
mYToNum[x取[0,x)， y对应最大套娃数量
vector<pair<int, int>> vYNum当前x，各y对应数量

注意：

x相同，无法套娃，所以必须等当前x处理完毕，才能更新mYToNum。
y值越大，对应的数量越大，否则被淘汰了。所以mYToNum的键和值都是升序。
y小于当前y的，不会淘汰当前y，因为当前长度就是小于y的最大长度+1。
所以只会被相等的y淘汰。
当前y 可能淘汰比当前y大的。

代码

class Solution {
public:
int maxEnvelopes(vector<vector>& envelopes) {
std::map<int, vector> mXToYS;
for (const auto& v : envelopes)
{
mXToYS[v[0]].emplace_back(v[1]);
}
std::map<int, int> mYToNum;//y值对应最大数量
int iMax = 0;
for (const auto& it : mXToYS)
{
vector<pair<int, int>> vYNum;
for (const auto& y : it.second)
{
const auto it = mYToNum.lower_bound(y);
const int num = 1 + ((mYToNum.begin() == it) ? 0 : std::prev(it)->second);
iMax = max(iMax, num);
vYNum.emplace_back(y, num);
}
for(const auto[y,num]: vYNum)
{
const auto it = mYToNum.lower_bound(y);
auto ij = it;
for (; (ij != mYToNum.end()) && (ij->second <= num); ++ij);
mYToNum.erase(it, ij);
if (!mYToNum.count(y))
{
mYToNum[y] = num;
}
}
}
return iMax;
}
};

2023年1月旧代码

class Solution {
public:
int maxEnvelopes(vector<vector>& envelopes) {
std::map<int, vector> mWidthToHeights;
for (const auto& v : envelopes)
{
mWidthToHeights[v[0]].push_back(v[1]);
}
int iMax = 1;
std::map<int, int> mHeightNum;
for ( auto& it : mWidthToHeights)
{
sort(it.second.begin(), it.second.end(),std::greater());
for (auto& height : it.second)
{
auto it = mHeightNum.lower_bound(height);
int iNum =1;
if (mHeightNum.begin() != it)
{//没有套
auto ij = it;
–ij;
iNum = ij->second + 1;
}
iNum = max(iNum,mHeightNum[height]);
auto ij = it;
while ( (ij != mHeightNum.end())&& ( ij->second < iNum))
{
ij++;
}
mHeightNum.erase(it, ij);
mHeightNum[height] = max(mHeightNum[height], iNum);
iMax = max(iMax, mHeightNum[height]);
}
}
return iMax;
}
};

扩展阅读

视频课程

有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步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.chinasem.cn/article/336945。

相关文章

Windows下C++使用SQLitede的操作过程

Windows下C++使用SQLitede的操作过程

《Windows下C++使用SQLitede的操作过程》本文介绍了Windows下C++使用SQLite的安装配置、CppSQLite库封装优势、核心功能（如数据库连接、事务管理）、跨平台支持及性能优... 目录Windows下C++使用SQLite1、安装2、代码示例CppSQLite：C++轻松操作SQ
阅读更多...
C++中RAII资源获取即初始化

C++中RAII资源获取即初始化

《C++中RAII资源获取即初始化》RAII通过构造/析构自动管理资源生命周期,确保安全释放,本文就来介绍一下C++中的RAII技术及其应用,具有一定的参考价值,感兴趣的可以了解一下... 目录一、核心原理与机制二、标准库中的RAII实现三、自定义RAII类设计原则四、常见应用场景1. 内存管理2. 文件操
阅读更多...
C++中零拷贝的多种实现方式

C++中零拷贝的多种实现方式

《C++中零拷贝的多种实现方式》本文主要介绍了C++中零拷贝的实现示例,旨在在减少数据在内存中的不必要复制,从而提高程序性能、降低内存使用并减少CPU消耗,零拷贝技术通过多种方式实现,下面就来了解一下... 目录一、C++中零拷贝技术的核心概念二、std::string_view 简介三、std::stri
阅读更多...
C++高效内存池实现减少动态分配开销的解决方案

C++高效内存池实现减少动态分配开销的解决方案

《C++高效内存池实现减少动态分配开销的解决方案》C++动态内存分配存在系统调用开销、碎片化和锁竞争等性能问题,内存池通过预分配、分块管理和缓存复用解决这些问题,下面就来了解一下... 目录一、C++内存分配的性能挑战二、内存池技术的核心原理三、主流内存池实现：TCMalloc与Jemalloc1. TCM
阅读更多...
C++ 函数 strftime 和时间格式示例详解

C++ 函数 strftime 和时间格式示例详解

《C++函数strftime和时间格式示例详解》strftime是C/C++标准库中用于格式化日期和时间的函数,定义在ctime头文件中,它将tm结构体中的时间信息转换为指定格式的字符串,是处理... 目录C++ 函数 strftipythonme 详解一、函数原型二、功能描述三、格式字符串说明四、返回值五
阅读更多...
MySQL 设置AUTO_INCREMENT 无效的问题解决

MySQL 设置AUTO_INCREMENT 无效的问题解决

《MySQL设置AUTO_INCREMENT无效的问题解决》本文主要介绍了MySQL设置AUTO_INCREMENT无效的问题解决,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参... 目录快速设置mysql的auto_increment参数一、修改 AUTO_INCREMENT 的值。
阅读更多...
关于跨域无效的问题及解决(java后端方案)

关于跨域无效的问题及解决(java后端方案)

《关于跨域无效的问题及解决(java后端方案)》：本文主要介绍关于跨域无效的问题及解决(java后端方案),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录通用后端跨域方法1、@CrossOrigin 注解2、springboot2.0 实现WebMvcConfig
阅读更多...
C++作用域和标识符查找规则详解

C++作用域和标识符查找规则详解

《C++作用域和标识符查找规则详解》在C++中,作用域（Scope）和标识符查找（IdentifierLookup）是理解代码行为的重要概念,本文将详细介绍这些规则,并通过实例来说明它们的工作原理,需... 目录作用域标识符查找规则1. 普通查找（Ordinary Lookup）2. 限定查找（Qualif
阅读更多...
Go语言中泄漏缓冲区的问题解决

Go语言中泄漏缓冲区的问题解决

《Go语言中泄漏缓冲区的问题解决》缓冲区是一种常见的数据结构,常被用于在不同的并发单元之间传递数据,然而,若缓冲区使用不当,就可能引发泄漏缓冲区问题,本文就来介绍一下问题的解决,感兴趣的可以了解一下... 目录引言泄漏缓冲区的基本概念代码示例：泄漏缓冲区的产生项目场景：Web 服务器中的请求缓冲场景描述代码
阅读更多...
Java死锁问题解决方案及示例详解

Java死锁问题解决方案及示例详解

《Java死锁问题解决方案及示例详解》死锁是指两个或多个线程因争夺资源而相互等待,导致所有线程都无法继续执行的一种状态,本文给大家详细介绍了Java死锁问题解决方案详解及实践样例,需要的朋友可以参考下... 目录1、简述死锁的四个必要条件：2、死锁示例代码3、如何检测死锁？3.1 使用 jstack3.2
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2