C++单调向量算法:132 模式解法三枚举1

简介: C++单调向量算法:132 模式解法三枚举1

本题不同解法

分析

时间复杂度

2轮循环时间复杂度都是O(n)。

步骤

第一步

枚举32,再将2to3,转成3to2。枚举2。v3ValueIndex|记录nums[0,k)所有的值的索引。然后在v3ValueIndex中寻找值大于iValue,如果有多个结果取索引最大的。如果value0 <= value1且index0 <= index1,则value0被index0淘汰。能选取vaule0则必定能选择vaule1,而index1比index0大。淘汰后,值按降序排序,3Index按升序排序。由于索引是越来越大,所以只会淘汰旧值,不会被旧值淘汰。由于淘汰值小的,所以可以从末尾淘汰。按索引升序插入,而索引是按升序排序的,所以插入也在末尾。故可以用栈或向量代替有序映射。在尾部增加、删除时间复杂度都是O(1)。

第二步

枚举1。如果m3IndexTo2Value(i,m_c)中存在比nums[i]大的值,则存在132模式,否则不存在。注意:m3IndexTo2Value 有些key会不存在。std::unordered_map不存在的值是0,而本题的值可能是负数。

关于2to3转成3to2

计算2to3的过程中,会淘汰一些组合,不影响结果。2to3转成3to2的时候,也会淘汰一些组合,被淘汰的不影响最终结果。m3IndexTo2Value, 3Index相同,淘汰值小的。如果值小的都大于nums[i],那么值的一定大于nums[i]。我们只要确保没被淘汰的组合都被枚举到,旧可以了。

代码

核心代码

class Solution {
public:
  bool find132pattern(vector<int>& nums) {
    m_c = nums.size();
    const int iNotMayMinValue = -1000 * 1000 * 1000 - 1;
    {
      vector < std::pair<int, int>> v3ValueIndex;//3Value的值按降序排序,3Index按升序排序
      for (int k =0 ; k < m_c ; k++ )
      {
        const int& iValue = nums[k];
        while (v3ValueIndex.size() && (v3ValueIndex.back().first <= iValue))
        {
          v3ValueIndex.pop_back();
        }
        if (v3ValueIndex.size())
        {
          const int i3Index = v3ValueIndex.back().second;
          if (!m3IndexTo2Value.count(i3Index) || (m3IndexTo2Value[i3Index] < iValue))
          {
            m3IndexTo2Value[i3Index] = iValue;
          }
        }
        v3ValueIndex.emplace_back(iValue, k);
      }
    }
    //寻找1,即nums[i]
    {
      int iMaxTow = iNotMayMinValue;
      for (int i = m_c - 1; i >= 0; i--)
      {
        const int& iValue = nums[i];
        if( iMaxTow > iValue )
        {
          m_iIndex1 = i;
          return true;
        }
        if (m3IndexTo2Value.count(i))
        {
          iMaxTow = max(iMaxTow, m3IndexTo2Value[i]);
        }
      }
    }
    return false;
  }
  std::unordered_map<int, int> m3IndexTo2Value;
  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 C++17

或者 操作系统:win10 开发环境: VS2022 C++17


相关文章
|
1月前
|
存储 算法 C++
高精度算法(加、减、乘、除,使用c++实现)
高精度算法(加、减、乘、除,使用c++实现)
406 0
高精度算法(加、减、乘、除,使用c++实现)
|
30天前
|
前端开发 算法 JavaScript
无界SaaS模式深度解析:算力算法、链接力、数据确权制度
私域电商的无界SaaS模式涉及后端开发、前端开发、数据库设计、API接口、区块链技术、支付和身份验证系统等多个技术领域。本文通过简化框架和示例代码,指导如何将核心功能转化为技术实现,涵盖用户管理、企业店铺管理、数据流量管理等关键环节。
|
1月前
|
存储 算法 决策智能
【算法】博弈论(C/C++)
【算法】博弈论(C/C++)
|
1月前
|
存储 算法 C++
【算法】哈希映射(C/C++)
【算法】哈希映射(C/C++)
|
1月前
|
机器学习/深度学习 人工智能 算法
【算法】最长公共子序列(C/C++)
【算法】最长公共子序列(C/C++)
|
1月前
|
人工智能 算法 BI
一篇带你速通差分算法(C/C++)
一篇带你速通差分算法(C/C++)
|
24天前
|
算法 安全 数据安全/隐私保护
基于game-based算法的动态频谱访问matlab仿真
本算法展示了在认知无线电网络中,通过游戏理论优化动态频谱访问,提高频谱利用率和物理层安全性。程序运行效果包括负载因子、传输功率、信噪比对用户效用和保密率的影响分析。软件版本:Matlab 2022a。完整代码包含详细中文注释和操作视频。
|
9天前
|
算法 数据挖掘 数据安全/隐私保护
基于FCM模糊聚类算法的图像分割matlab仿真
本项目展示了基于模糊C均值(FCM)算法的图像分割技术。算法运行效果良好,无水印。使用MATLAB 2022a开发,提供完整代码及中文注释,附带操作步骤视频。FCM算法通过隶属度矩阵和聚类中心矩阵实现图像分割,适用于灰度和彩色图像,广泛应用于医学影像、遥感图像等领域。
|
10天前
|
算法 调度
基于遗传模拟退火混合优化算法的车间作业最优调度matlab仿真,输出甘特图
车间作业调度问题(JSSP)通过遗传算法(GA)和模拟退火算法(SA)优化多个作业在并行工作中心上的加工顺序和时间,以最小化总完成时间和机器闲置时间。MATLAB2022a版本运行测试,展示了有效性和可行性。核心程序采用作业列表表示法,结合遗传操作和模拟退火过程,提高算法性能。
|
11天前
|
存储 算法 决策智能
基于免疫算法的TSP问题求解matlab仿真
旅行商问题(TSP)是一个经典的组合优化问题,目标是寻找经过每个城市恰好一次并返回起点的最短回路。本文介绍了一种基于免疫算法(IA)的解决方案,该算法模拟生物免疫系统的运作机制,通过克隆选择、变异和免疫记忆等步骤,有效解决了TSP问题。程序使用MATLAB 2022a版本运行,展示了良好的优化效果。