迹忆客 专注技术分享

当前位置:主页 > 学无止境 > 编程语言 > Python >

Python 中的最长递增子序列

作者:迹忆客 最近更新:2023/06/16 浏览次数:

我们将学习什么是子序列,以及如何使用 Python 中的 n 平方方法和二分搜索方法计算数组中最长的递增子序列。


使用 N 平方方法计算 Python 中的最长递增子序列

一个著名的问题被问及 Python 社区中最长的增长子序列,并在不同的采访中被问及。 这是一个 Leetcode 问题,问题是:给定一个未排序的整数数组,并找到给定数组的最长递增子序列或子集的长度。

子集就像数组的短数组; 每个数组可以有多个子集。 另一件事是子数组将是此 [10,9,2,5,3,7,101,18] 数组中的一些元素,但以连续的子序列方式。

可以是[2, 3, 5, 7],但不能是[2,3,101],所以讨论子数组时不需要打断序列。 并且,随后,元素在数组中出现的顺序必须相同,但可以是任何一个。

例如,在本例中,正如我们所见,答案是 [2, 3, 7,101]; 5 不存在,但这没关系,因为它是一个子序列。

如果我们从 [10,9,2,5,3,7,101,18] 中看到最长的递增子序列,我们会找到 [2, 5, 7, 101]; 这也可能意味着一个答案,但答案也可能是 [2, 3, 7, 101] 这也是我们的另一个子序列。 [3, 7, 101] 也是一个子序列,但不是最长的,所以不考虑。

可能有不止一种组合; 正如我们刚刚看到的,我们只需要返回长度。

通过这个例子,我们可以很容易地想到一个递归解决方案,从零索引开始,沿着所有不同的路径前进。 使用这个数组 [0,3,1,6,2,2,7],我们可以采取,例如,对于 0,我们可以转到 3,或者我们可以转到 1 或转到 6。

然后,从那时起,递归地继续。 看下面的例子,哪条路径是最长的,它将是指数级的; 我们很容易认为必须有一些动态编程方法。

所以,我们有一个数组,其中每个索引至少有一个长度。

[0,3,1,6,2,2,7]
[1,1,1,1,1,1,1]

我们将从第一个索引 0 开始,其长度为 1,但是对于 3,我们可以向后看,如果 3 大于 0,则 3 有 2 个长度。 如果我们再次使用 1,我们将查看当前索引之前的所有索引。

从零索引可以看出,1大于0,但1不大于3,所以此时我们计算0和1,它们的长度为2。

[0,3,1,6,2,2,7]
[1,2,2,1,1,1,1]

在考虑6的时候,我们从头往后看,我们知道6大于[0,1]或者[0,3],加上6,它的长度就是3那么2的长度也是3,以此类推 对了,这是一个平方的方法。

[0,3,1,6,2,2,7]
[1,2,2,3,3,...]

时间复杂度和空间复杂度

让我们进入代码并创建名为 CalculateSubSequence 的类; 在 lengthOfLIS 函数中,我们将 nums_list 变量初始化为 nums 的长度,数组的长度仅为 1 次。

在嵌套循环中,我们将检查值是否大于我们正在检查的数字。 然后,让我们取 i 的 nums_list,我们将更新 nums_list 值,同时使用 nums_list[i] 取最大值。

i 在从外循环迭代之后出现,对于 nums_list[j],j 在从内循环迭代之后出现,然后我们将它加 1。 最后,我们返回 nums_list 的最大值。

class CalculateSubSequence:

    def lengthOfLIS(self, nums: list[int]) -> int:

        nums_list = [1] * len(nums)

        for i in range(len(nums)-1, -1, -1):

            for j in range(i+1, len(nums)):

                if nums[i] < nums[j]:

                    nums_list[i] = max(nums_list[i], nums_list[j] + 1)

        return max(nums_list)

sbs = CalculateSubSequence()
sbs.lengthOfLIS([0,3,1,6,2,2,7])

这里时间复杂度是 n 的平方,空间复杂度是 n 的 o。

4

上面的解决方案就足够了,但另一种方法 n log 使用 bisect_left 对临时数组的左侧进行二进制搜索。

from bisect import bisect_left

class CalculateSubSequence:

    def lengthOfLIS(self, nums: list[int]) -> int:
        n= len(nums)
        tmp=[nums[0]]
        for n in nums:
            x = bisect_left(tmp,n)
            if x ==len(tmp):
                tmp.append(n)
            elif tmp[x]>n:
                tmp[x]=n
        return len(tmp)

sbs = CalculateSubSequence()
sbs.lengthOfLIS([0,3,1,6,2,2,7])

输出:

4

上一篇:使用 Python 将文件上传到 Google 云端硬盘

下一篇:没有了

转载请发邮件至 1244347461@qq.com 进行申请,经作者同意之后,转载请以链接形式注明出处

本文地址:

相关文章

Python 子进程捕获输出

发布时间:2023/06/15 浏览次数:136 分类:Python

本文的主要目的是演示如何在 Python 中捕获、存储和显示子进程的输出。Python 子进程捕获输出 Subprocess 是一个内置的 Python 模块,预装了 Python 安装文件。

Python 子进程在运行时读取标准输出

发布时间:2023/06/15 浏览次数:129 分类:Python

本文的主要目的是演示如何读取在 Python 中执行的子进程的标准输出。Python 子进程在运行时读取标准输出 与许多其他内置模块一样,Subprocess 也是一个内置模块,预装了“正常”Python 安装。

使用 Python 获取 CPU 数量

发布时间:2023/06/15 浏览次数:173 分类:Python

CPU 可以包含单核或多核。 单核只处理一个进程,而多核同时处理多个进程。本篇文章将介绍使用 Python 程序查找 CPU 内核总数的不同方法。使用 multiprocessing 模块获取 Python 中的 CPU 数量

Python获取CPU温度

发布时间:2023/06/15 浏览次数:111 分类:Python

本文的主要目的是演示如何借助 Python 中的 pythonnet 库读取和显示 CPU 温度。Python获取CPU温度

Python 从网页中提取表格

发布时间:2023/06/15 浏览次数:50 分类:Python

本文的主要目的是演示如何在 Python 中使用 Pandas 和 lxml 从网页中提取表格。Python 从网页中提取表格

Python Antigravity 模块的用途

发布时间:2023/06/15 浏览次数:72 分类:Python

一个这样的 Python 彩蛋是反重力模块。让我们看看 Antigravity 模块做了什么,并看看其他几个例子。

不使用 pip 安装 Python 包

发布时间:2023/06/15 浏览次数:189 分类:Python

在本文中,我们将学习如何在 Python 中安装没有 pip 的库。 我们还将学习如何使用 conda 命令在 Python 中安装包。不使用 pip 命令安装 Python 库

在代码中安装 Python 模块

发布时间:2023/06/15 浏览次数:72 分类:Python

理想情况下,从 pip 安装 Python 模块非常方便; 为此,您必须在活动终端中输入 pip install module-name ,然后就完成了。

扫一扫阅读全部技术教程

社交账号
  • https://www.github.com/onmpw
  • qq:1244347461

最新推荐

教程更新

热门标签

扫码一下
查看教程更方便