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

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

说明

本篇是视频课程的讲义,可以看直接查看视频。也可以下载源码,包括空源码。

本文涉及的基础知识点

二分查找算法合集

本题不同解法

题目

给你一个整数数组 nums ,数组中共有 n 个整数。132 模式的子序列由三个整数 nums[i]nums[j] nums[k] 组成,并同时满足:i < j < k nums[i] < nums[k] < nums[j]

如果 nums 中存在 132 模式的子序列,返回 true ;否则,返回 false

示例 1

输入:nums = [1,2,3,4]

输出:false

解释:序列中不存在 132 模式的子序列。

示例 2

输入:nums = [3,1,4,2]

输出:true

解释:序列中有 1 132 模式的子序列: [1, 4, 2]

示例 3

输入:nums = [-1,3,2,0]

输出:true

解释:序列中有 3 132 模式的的子序列:[-1, 3, 2][-1, 3, 0] [-1, 2, 0]

参数范围

n == nums.length

1 <= n <= 2 * 105

-109 <= nums[i] <= 109

分析

分两步。

第一步计算12存储到m_v2To1。m_v2To1[j]等于i表示nums[j] >=nsum[i],如果有多个合法的i,取最小值,如果不存在,m_v2To1[j]=m_c。mValueIndexkey对应数组值nums[i]value对应数组索引ii[0,j)。由于是从左向右寻找小于某数的数,如果i1>=i0,且nums[i1] >= nums[i0],则i1被淘汰。淘汰后,mValueIndex中的数组值按升序排序,数组索引按降序排序。如果mValueIndex中存在数组值小于iValue的数,那说明存在值、索引都比i小的数,i被淘汰。大于等于i的索引还未添加。如果不存在,不需要判断当前值和索引是否淘汰已有值,因为:索引是按从小到大添加的。添加时需要判断当真值,是否存在。如果存在,则其索引一定小于当前索引,无需添加。

第二步,遍历m_v2To1,寻找是否存在kmValueIndexkey对应数组值nums[k]value对应数组索引kj[0,i)。由于是从右向左寻找大于某数的数,所以数组值和索引都小的值和索引被淘汰。淘汰后,mValueIndex中的数组值按升序排序,数组索引按降序排序。由于mValueIndex已有数据中的索引小于当前索引,所以只需要考虑淘汰旧值(数组值小于等于当前数组值)。k需要符合以下三个条件:

条件一

nums[k] > nums[j]

条件二

k > i(即v2To1[j])

条件三

k < j (一定符合,不符合的还没添加)

auto it = mValueIndex.upper_bound(iValue);

后[it, mValueIndex.end()) 都符合条件一,由于索引是降序排序,所以只需要判断it->second是否大于i

核心代码

class Solution {
public:
         bool find132pattern(vector<int>& nums) {
                   m_c = nums.size();
                   m_v2To1.assign(m_c, m_c);
                   {
                            map<int, int> mValueIndex;//key按升序,value按降序排序
                            for (int j = 0; j < m_c; j++)
                            {
                                     const int iValue = nums[j];
                                     auto it = mValueIndex.lower_bound(iValue);
                                      if (mValueIndex.begin() != it)
                                     {
                                               auto itPre = std::prev(it);
                                               m_v2To1[j] = itPre->second;
                                               continue;//key和value都小于等于iValue和i,i被淘汰
                                     }
                                     //删除key和value都大于等于iValue和i
                                     if (!mValueIndex.count(nums[j]))
                                     {
                                               mValueIndex[nums[j]] = j;
                                     }
                            }
                   }
                   //遍历v[2],看是否存在3
                   {
                            map<int, int> mValueIndex;//132的3,从右向左找大于2的值。key按升序,value按降序排序
                            for (int j = 0; j < m_c; j++)
                            {
                                     const int iValue = nums[j];
                                     auto it = mValueIndex.upper_bound(iValue);
                                     if (mValueIndex.end() != it)
                                     {
                                               if (it->second > m_v2To1[j])
                                               {
                                                        m_iIndex3 = it->second;
                                                        return true;
                                               }
                                     }
                                     while (mValueIndex.size() && (mValueIndex.begin()->first <= iValue))
                                     {
                                               mValueIndex.erase(mValueIndex.begin());
                                     }
                                     mValueIndex[iValue] = j;
                            }
                   }
                   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<class T>
void Assert(const T& t1, const T& t2)
{
         assert(t1 == t2);
}
template<class T>
void Assert(const vector<T>& v1, const vector<T>& 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<int> nums;
         bool res;
         {
                   Solution slu;
                   nums = { 3,5,0,3,4 };          
                   res = slu.find132pattern(nums);
                   Assert(vector<int>{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<int>{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<int>{4, 0, 0, 0}, slu.m_v2To1);
                   Assert(1, slu.m_iIndex3);
                   Assert(true, res);
         }
         //CConsole::Out(res);
}

其它

学院课程

基础算法的C++实现课程,请点击下面的CSDN学院的链接。讲义有算法详解。

2024年1月15之前完全免费,之后绝大部分免费

https://edu.csdn.net/course/detail/38771

C#入职培训

此课程的目的:让新同事更快完成从学生到C#程序员的转换,更快上手完成C#的开发工作。

https://edu.csdn.net/course/detail/38768

C++入职培训

让新同事更快完成从学生到C++程序员的转换,更快上手完成C++的开发工作。

https://edu.csdn.net/course/detail/32049

运行验证环境

Win10 VS2022 Ck++17 或win7 VS2019 C++17

每天都补充正能量

好好学习,天天向上。

事无终始,无务多业。

是故置本不安者,无务丰末。

相关下载

如果你时间宝贵,只想看精华,请到CSDN下载频道下载《闻缺陷则喜算法册》doc版

https://download.csdn.net/download/he_zhidan/88348653


目录
打赏
0
0
0
0
36
分享
相关文章
解读 C++ 助力的局域网监控电脑网络连接算法
本文探讨了使用C++语言实现局域网监控电脑中网络连接监控的算法。通过将局域网的拓扑结构建模为图(Graph)数据结构,每台电脑作为顶点,网络连接作为边,可高效管理与监控动态变化的网络连接。文章展示了基于深度优先搜索(DFS)的连通性检测算法,用于判断两节点间是否存在路径,助力故障排查与流量优化。C++的高效性能结合图算法,为保障网络秩序与信息安全提供了坚实基础,未来可进一步优化以应对无线网络等新挑战。
基于 C++ 语言的迪杰斯特拉算法在局域网计算机管理中的应用剖析
在局域网计算机管理中,迪杰斯特拉算法用于优化网络路径、分配资源和定位故障节点,确保高效稳定的网络环境。该算法通过计算最短路径,提升数据传输速率与稳定性,实现负载均衡并快速排除故障。C++代码示例展示了其在网络模拟中的应用,为企业信息化建设提供有力支持。
42 15
公司局域网管理中的哈希表查找优化 C++ 算法探究
在数字化办公环境中,公司局域网管理至关重要。哈希表作为一种高效的数据结构,通过哈希函数将关键值(如IP地址、账号)映射到数组索引,实现快速的插入、删除与查找操作。例如,在员工登录验证和设备信息管理中,哈希表能显著提升效率,避免传统线性查找的低效问题。本文以C++为例,展示了哈希表在局域网管理中的具体应用,包括设备MAC地址与IP分配的存储与查询,并探讨了优化哈希函数和扩容策略,确保网络管理高效准确。
|
2月前
|
【C++数据结构——查找】二分查找(头歌实践教学平台习题)【合集】
二分查找的基本思想是:每次比较中间元素与目标元素的大小,如果中间元素等于目标元素,则查找成功;顺序表是线性表的一种存储方式,它用一组地址连续的存储单元依次存储线性表中的数据元素,使得逻辑上相邻的元素在物理存储位置上也相邻。第1次比较:查找范围R[0...10],比较元素R[5]:25。第1次比较:查找范围R[0...10],比较元素R[5]:25。第2次比较:查找范围R[0..4],比较元素R[2]:10。第3次比较:查找范围R[3...4],比较元素R[3]:15。,其中是顺序表中元素的个数。
153 68
【C++数据结构——查找】二分查找(头歌实践教学平台习题)【合集】
|
25天前
|
算法系列之搜素算法-二分查找
二分查找是一种在`有序`数组中查找特定元素的算法。它的基本思想是通过将数组分成两半,逐步缩小查找范围,直到找到目标元素或确定目标元素不存在。
30 9
算法系列之搜素算法-二分查找
员工屏幕监控系统之 C++ 图像差分算法
在现代企业管理中,员工屏幕监控系统至关重要。本文探讨了其中常用的图像差分算法,该算法通过比较相邻两帧图像的像素差异,检测屏幕内容变化,如应用程序切换等。文中提供了C++实现代码,并介绍了其在实时监控、异常行为检测和数据压缩等方面的应用,展示了其实现简单、效率高的特点。
57 15
从集思录可转债数据探秘:Python与C++实现的移动平均算法应用
本文探讨了如何利用移动平均算法分析集思录提供的可转债数据,帮助投资者把握价格趋势。通过Python和C++两种编程语言实现简单移动平均(SMA),展示了数据处理的具体方法。Python代码借助`pandas`库轻松计算5日SMA,而C++代码则通过高效的数据处理展示了SMA的计算过程。集思录平台提供了详尽且及时的可转债数据,助力投资者结合算法与社区讨论,做出更明智的投资决策。掌握这些工具和技术,有助于在复杂多变的金融市场中挖掘更多价值。
57 12
|
23天前
|
公司监控上网软件架构:基于 C++ 链表算法的数据关联机制探讨
在数字化办公时代,公司监控上网软件成为企业管理网络资源和保障信息安全的关键工具。本文深入剖析C++中的链表数据结构及其在该软件中的应用。链表通过节点存储网络访问记录,具备高效插入、删除操作及节省内存的优势,助力企业实时追踪员工上网行为,提升运营效率并降低安全风险。示例代码展示了如何用C++实现链表记录上网行为,并模拟发送至服务器。链表为公司监控上网软件提供了灵活高效的数据管理方式,但实际开发还需考虑安全性、隐私保护等多方面因素。
23 0
公司监控上网软件架构:基于 C++ 链表算法的数据关联机制探讨
探秘:基于 C++ 的局域网电脑控制软件自适应指令分发算法
在现代企业信息化架构中,局域网电脑控制软件如同“指挥官”,通过自适应指令分发算法动态调整指令发送节奏与数据量,确保不同性能的终端设备高效运行。基于C++语言,利用套接字实现稳定连接和线程同步管理,结合实时状态反馈,优化指令分发策略,提升整体管控效率,保障网络稳定,助力数字化办公。
72 19