广州app网站建设,政务网站建设原则,营销型网站建设主要需要注意什么,网站网页设计海报图片本文涉及的基础知识点
二分查找算法合集
本题不同解法
包括题目及代码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代码更简洁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(vectorintnums) {m_c nums.size();if (m_c 3){m_iIndex3 -1;return false;}int iLeftMin nums.front();std::multisetint 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[j1]));}return false;}vectorint 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
我想对大家说的话闻缺陷则喜是一个美好的愿望早发现问题早修改问题给老板节约钱。墨子曰事无终始无务多业。也就是我们常说的专业的人做专业的事。如果程序是一条龙那算法就是他的是睛
