阿里云网站建设程序,制作网站需要的技术,百度链接,上海建立网站公司本文涉及的基础知识点
二分查找算法合集
本题不同解法
包括题目及代码C二分查找算法#xff1a;132 模式解法一枚举3C二分查找算法#xff1a;132 模式解法二枚举2代码最简洁C二分查找算法#xff1a;132 模式解法三枚举1性能最佳C单调向量算法#xff1a;132 模式解法三…本文涉及的基础知识点
二分查找算法合集
本题不同解法
包括题目及代码C二分查找算法132 模式解法一枚举3C二分查找算法132 模式解法二枚举2代码最简洁C二分查找算法132 模式解法三枚举1性能最佳C单调向量算法132 模式解法三枚举1
分析
时间复杂度
两轮循环时间复杂度都是O(nlogn)。
步骤
第一轮枚举3nums(j,m_c)中小于nums[j]的元素都可以成为2如果有多个合法2选择最大的2。如果不存在2设置成比最小值还小的值。[begin,it)是所有合法的2由于是升序最大的2就是最后一个。 第二轮枚举1nums(i,m_c)中的3对应的2 大于nums[i]则有结果否则无解。
代码
核心代码
class Solution {
public:bool find132pattern(vectorint nums) {m_c nums.size();const int iNotMayMinValue -1000 * 1000 * 1000 - 1;{std::setint set2;for (int j m_c-1; j 0 ; j-- ){const int iValue nums[j];auto it set2.lower_bound(iValue);m3To2[iValue] (set2.begin() ! it) ? *std::prev(it) : iNotMayMinValue;set2.emplace(iValue);}}//寻找1即nums[i]{ std::setint set2;for (int i m_c-1 ; i 0 ; i-- ){const int iValue nums[i];auto it set2.upper_bound(iValue);if (set2.end() ! it){m_iIndex1 i;return true;}set2.emplace(m3To2[iValue]);}}return false;}std::unordered_mapint, int m3To2;int m_iIndex1 -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_v3To1); Assert(0, slu.m_iIndex1); 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_v3To1); Assert(1, slu.m_iIndex1); Assert(true, res); } { Solution slu; nums { -1,3,2,0 }; res slu.find132pattern(nums); //Assert(vector{4, 0, 0, 0}, slu.m_v3To1); Assert(0, slu.m_iIndex1); Assert(true, res); }
{Solution slu;nums { 1, 0, 1, -4, -3 };res slu.find132pattern(nums);//Assert(vector{4, 0, 0, 0}, slu.m_v3To1);Assert(-1, slu.m_iIndex1);Assert(false, 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
洒家想对大家说的话闻缺陷则喜是一个美好的愿望早发现问题早修改问题给老板节约钱。墨家名称的来源有所得以墨记之。如果程序是一条龙那算法就是他的是睛
测试环境
操作系统win7 开发环境 VS2019 C17 或者 操作系统win10 开发环境 VS2022 C17
