C++二分查找算法:132模式枚举3简洁版

2023-11-21 07:44

本文主要是介绍C++二分查找算法:132模式枚举3简洁版,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

本文涉及的基础知识点

二分查找算法合集

本题不同解法

包括题目及代码C++二分查找算法:132 模式解法一枚举3
C++二分查找算法:132 模式解法二枚举2
代码简洁C++二分查找算法:132 模式解法三枚举1
性能最佳C++单调向量算法:132 模式解法三枚举1
代码更简洁C++二分查找算法:132模式枚举3简洁版

分析

时间复杂度

总时间复杂度O(nlogn),枚举3时间复杂度O(n),查询2是否复杂度O(logn)。

思路

如果有多个候选1,选取最小的那个,所以我们不需要记录所有的1,只需要记录最小值iLeftMin。2必须大于iLeftMin,且小于3。
也就是setRight中第一个大于iLeftMin的数,是否小于nums[j]。

核心代码

class Solution{
public:bool find132pattern(vector<int>&nums) {m_c = nums.size();if (m_c < 3){m_iIndex3 = -1;return false;}int iLeftMin = nums.front();std::multiset<int> setRight(nums.begin()+2,nums.end());for (int j = 1; j + 1 < m_c; j++){auto it = setRight.upper_bound(iLeftMin);if ((setRight.end() != it)&&(*it < nums[j])){m_iIndex3 = j;return true;}iLeftMin = min(iLeftMin, nums[j]);setRight.erase(setRight.find(nums[j+1]));}return false;}vector<int> m_v2To1;//v[i]等于j表示nums[i] >=nsum[j],如果有多个合法的j,取最小值,如果不存在,v[i]=m_c。int m_iIndex3 = -1;int m_c;
};

测试用例

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()
{
vector nums;
bool res;
{
Solution slu;
nums = { 3,5,0,3,4 };
res = slu.find132pattern(nums);
//Assert(vector{5, 0, 5, 2, 0}, slu.m_v2To1);
Assert(1, slu.m_iIndex3);
Assert(true, res);
}
{
nums = { 1 ,2, 3,4 };
res = Solution().find132pattern(nums);
Assert(false, res);
}
{
Solution slu;
nums = { 3,1,4,2 };
res = slu.find132pattern(nums);
//Assert(vector{4, 4, 0, 1}, slu.m_v2To1);
Assert(2, slu.m_iIndex3);
Assert(true, res);
}
{
Solution slu;
nums = { -1,3,2,0 };
res = slu.find132pattern(nums);
//Assert(vector{4, 0, 0, 0}, slu.m_v2To1);
Assert(1, slu.m_iIndex3);
Assert(true, res);
}
{
Solution slu;
nums = { 1, 4, 0, -1, -2, -3, -1, -2 };
res = slu.find132pattern(nums);
//Assert(vector{4, 0, 0, 0}, slu.m_v3To1);
//Assert(5, slu.m_iIndex3);
Assert(true, res);
}
{
Solution slu;
nums = { 2};
res = slu.find132pattern(nums);
//Assert(vector{5, 0, 5, 2, 0}, slu.m_v2To1);
Assert(-1, slu.m_iIndex3);
Assert(true, res);
}

//CConsole::Out(res);

}

扩展阅读

视频课程

有效学习:明确的目标 及时的反馈 拉伸区(难度合适),可以先学简单的课程,请移步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

我想对大家说的话
闻缺陷则喜是一个美好的愿望,早发现问题,早修改问题,给老板节约钱。
墨子曰:事无终始,无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙,那算法就是他的是睛

这篇关于C++二分查找算法:132模式枚举3简洁版的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!


原文地址:
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.chinasem.cn/article/400876

相关文章

C++中全局变量和局部变量的区别

《C++中全局变量和局部变量的区别》本文主要介绍了C++中全局变量和局部变量的区别,全局变量和局部变量在作用域和生命周期上有显著的区别,下面就来介绍一下,感兴趣的可以了解一下... 目录一、全局变量定义生命周期存储位置代码示例输出二、局部变量定义生命周期存储位置代码示例输出三、全局变量和局部变量的区别作用域

C++中assign函数的使用

《C++中assign函数的使用》在C++标准模板库中,std::list等容器都提供了assign成员函数,它比操作符更灵活,支持多种初始化方式,下面就来介绍一下assign的用法,具有一定的参考价... 目录​1.assign的基本功能​​语法​2. 具体用法示例​​​(1) 填充n个相同值​​(2)

c++ 类成员变量默认初始值的实现

《c++类成员变量默认初始值的实现》本文主要介绍了c++类成员变量默认初始值,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧... 目录C++类成员变量初始化c++类的变量的初始化在C++中,如果使用类成员变量时未给定其初始值,那么它将被

C++中NULL与nullptr的区别小结

《C++中NULL与nullptr的区别小结》本文介绍了C++编程中NULL与nullptr的区别,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编... 目录C++98空值——NULLC++11空值——nullptr区别对比示例 C++98空值——NUL

C++ Log4cpp跨平台日志库的使用小结

《C++Log4cpp跨平台日志库的使用小结》Log4cpp是c++类库,本文详细介绍了C++日志库log4cpp的使用方法,及设置日志输出格式和优先级,具有一定的参考价值,感兴趣的可以了解一下... 目录一、介绍1. log4cpp的日志方式2.设置日志输出的格式3. 设置日志的输出优先级二、Window

MySQL中查找重复值的实现

《MySQL中查找重复值的实现》查找重复值是一项常见需求,比如在数据清理、数据分析、数据质量检查等场景下,我们常常需要找出表中某列或多列的重复值,具有一定的参考价值,感兴趣的可以了解一下... 目录技术背景实现步骤方法一:使用GROUP BY和HAVING子句方法二:仅返回重复值方法三:返回完整记录方法四:

Java设计模式---迭代器模式(Iterator)解读

《Java设计模式---迭代器模式(Iterator)解读》:本文主要介绍Java设计模式---迭代器模式(Iterator),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,... 目录1、迭代器(Iterator)1.1、结构1.2、常用方法1.3、本质1、解耦集合与遍历逻辑2、统一

Java 线程安全与 volatile与单例模式问题及解决方案

《Java线程安全与volatile与单例模式问题及解决方案》文章主要讲解线程安全问题的五个成因(调度随机、变量修改、非原子操作、内存可见性、指令重排序)及解决方案,强调使用volatile关键字... 目录什么是线程安全线程安全问题的产生与解决方案线程的调度是随机的多个线程对同一个变量进行修改线程的修改操

Java中的雪花算法Snowflake解析与实践技巧

《Java中的雪花算法Snowflake解析与实践技巧》本文解析了雪花算法的原理、Java实现及生产实践,涵盖ID结构、位运算技巧、时钟回拨处理、WorkerId分配等关键点,并探讨了百度UidGen... 目录一、雪花算法核心原理1.1 算法起源1.2 ID结构详解1.3 核心特性二、Java实现解析2.

从入门到精通C++11 <chrono> 库特性

《从入门到精通C++11<chrono>库特性》chrono库是C++11中一个非常强大和实用的库,它为时间处理提供了丰富的功能和类型安全的接口,通过本文的介绍,我们了解了chrono库的基本概念... 目录一、引言1.1 为什么需要<chrono>库1.2<chrono>库的基本概念二、时间段(Durat