C++二分查找算法的应用:最长递增子序列

简介: C++二分查找算法的应用:最长递增子序列

本文涉及的基础知识点

二分查找算法合集

单调映射

源码下载

点击下载源码

题目

给你一个整数数组 nums ,找到其中最长严格递增子序列的长度。

子序列 是由数组派生而来的序列,删除(或不删除)数组中的元素而不改变其余元素的顺序。例如,[3,6,2,7] 是数组 [0,3,1,6,2,2,7] 的子序列。

示例 1:

输入:nums = [10,9,2,5,3,7,101,18]

输出:4

解释:最长递增子序列是 [2,3,7,101],因此长度为 4 。

示例 2:

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

输出:4

示例 3:

输入:nums = [7,7,7,7,7,7,7]

输出:1

参数范围

1 <= nums.length <= 2500

-104 <= nums[i] <=104

暴力解法

分析

m_vRet[i],记录以nums[i]结尾的最长严格递增系列。计算m_vRet[i]的方法:nums[j] < nums[i]中最大m_vRet[j]+1。如果不存在合法的j,则m_vRet[i]等于1。

下表以{1,2,6,5,4,5}

i

m_vRet[0,i),加粗表示nums[j]<nums[i]

m_vRet[i]

0

1

1

1

2{1,2}

2

1 2

3{1,2,6}

3

1 2 3

3{1,2,5}

4

1 2 3 3

3{1,2,4}

5

1 2 3 3 3

4{1,2,4,5}

两层循环,分别枚举i和j,故总时间复杂度是O(n2)。

代码

class Solution {
public:
         int lengthOfLIS(vector<int>& nums) {
                   m_c = nums.size();
                   m_vRet.resize(m_c);
                   for (int i = 0; i < m_c; i++)
                   {
                            int iPreLen = 0;
                            for (int j = 0; j < i; j++)
                            {
                                     if (nums[j] >= nums[i])
                                     {
                                               continue;
                                     }
                                     iPreLen = max(iPreLen, m_vRet[j]);
                            }
                            m_vRet[i] = iPreLen + 1;
                   }
                   return *std::max_element(m_vRet.begin(), m_vRet.end());
         }
         vector<int> m_vRet;
         int m_c;
};

有序映射

分析

如果nums[j1] > nums[j2],且m_vRet[j1] <= m_vRet[j2],那么j1被j2淘汰。以nums[j]为key,m_vRet[j]为值,创建有序映射。key和value都是升序。

下表以{1,2,6,5,4,5,5}为列来说明,加粗表示新增加,删除线表示删除。

{1,1}

{1,1},{2,2}

{1,1},{2,2},{6,3}

{1,1},{2,2},{5,3},{6,3}

{1,1},{2,2},{4,3},{5,3}

{1,1},{2,2},{4,3},{5,4}

{1,1},{2,2},{4,3},{5,4}

代码

class Solution {
public:
         int lengthOfLIS(vector<int>& nums) {
                   m_c = nums.size();
                   m_vRet.resize(m_c);
                   std::map<int, int> mValueLen = { {-1000 * 1000,0} };
                   for (int i = 0; i < m_c; i++)
                   {
                            //计算以nums[i]结尾的最长长度
                            auto it = mValueLen.lower_bound(nums[i]);
                            const int iLen = std::prev(it)->second + 1;
                            m_vRet[i] = iLen;
                            //如果nums[j] >= nums[j],且长度小于等于删除
                            auto ij = it;
                            for (; (ij != mValueLen.end()) && (ij->second <= iLen); ++ij);
                            mValueLen.erase(it, ij);
                            //如果nums[i]存在,说明旧值比当前值大,不能处理
                            if (!mValueLen.count(nums[i]))
                            {
                                     mValueLen[nums[i]] = iLen;
                            }
                   }
                   return *std::max_element(m_vRet.begin(), m_vRet.end());
         }
         vector<int> m_vRet;
         int m_c;
};

其它

学院课程

基础算法的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


相关文章
|
18小时前
|
机器学习/深度学习 算法
基于改进遗传优化的BP神经网络金融序列预测算法matlab仿真
本项目基于改进遗传优化的BP神经网络进行金融序列预测,使用MATLAB2022A实现。通过对比BP神经网络、遗传优化BP神经网络及改进遗传优化BP神经网络,展示了三者的误差和预测曲线差异。核心程序结合遗传算法(GA)与BP神经网络,利用GA优化BP网络的初始权重和阈值,提高预测精度。GA通过选择、交叉、变异操作迭代优化,防止局部收敛,增强模型对金融市场复杂性和不确定性的适应能力。
100 80
|
2月前
|
存储 并行计算 安全
C++多线程应用
【10月更文挑战第29天】C++ 中的多线程应用广泛,常见场景包括并行计算、网络编程中的并发服务器和图形用户界面(GUI)应用。通过多线程可以显著提升计算速度和响应能力。示例代码展示了如何使用 `pthread` 库创建和管理线程。注意事项包括数据同步与互斥、线程间通信和线程安全的类设计,以确保程序的正确性和稳定性。
|
2月前
|
算法
动态规划算法学习四:最大上升子序列问题(LIS:Longest Increasing Subsequence)
这篇文章介绍了动态规划算法中解决最大上升子序列问题(LIS)的方法,包括问题的描述、动态规划的步骤、状态表示、递推方程、计算最优值以及优化方法,如非动态规划的二分法。
80 0
动态规划算法学习四:最大上升子序列问题(LIS:Longest Increasing Subsequence)
|
2月前
|
存储 编译器 C++
【C++篇】揭开 C++ STL list 容器的神秘面纱:从底层设计到高效应用的全景解析(附源码)
【C++篇】揭开 C++ STL list 容器的神秘面纱:从底层设计到高效应用的全景解析(附源码)
82 2
|
3月前
|
存储 算法 安全
超级好用的C++实用库之sha256算法
超级好用的C++实用库之sha256算法
139 1
|
3月前
|
编译器 C++
【C++核心】函数的应用和提高详解
这篇文章详细讲解了C++函数的定义、调用、值传递、常见样式、声明、分文件编写以及函数提高的内容,包括函数默认参数、占位参数、重载等高级用法。
31 3
|
2月前
|
算法 数据处理 C++
c++ STL划分算法;partition()、partition_copy()、stable_partition()、partition_point()详解
这些算法是C++ STL中处理和组织数据的强大工具,能够高效地实现复杂的数据处理逻辑。理解它们的差异和应用场景,将有助于编写更加高效和清晰的C++代码。
47 0
|
3月前
|
算法 数据可视化
基于SSA奇异谱分析算法的时间序列趋势线提取matlab仿真
奇异谱分析(SSA)是一种基于奇异值分解(SVD)和轨迹矩阵的非线性、非参数时间序列分析方法,适用于提取趋势、周期性和噪声成分。本项目使用MATLAB 2022a版本实现从强干扰序列中提取趋势线,并通过可视化展示了原时间序列与提取的趋势分量。代码实现了滑动窗口下的奇异值分解和分组重构,适用于非线性和非平稳时间序列分析。此方法在气候变化、金融市场和生物医学信号处理等领域有广泛应用。
202 19
|
2月前
|
存储 算法 程序员
迪杰斯特拉(Dijkstra)算法(C/C++)
迪杰斯特拉(Dijkstra)算法(C/C++)
|
2月前
|
人工智能 算法 Java
【搜索算法】数字游戏(C/C++)
【搜索算法】数字游戏(C/C++)