Python中最长的递增序列

如何使用Python中的N平方法和二进制搜索法计算一个数组中最长的递增子序列。

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

在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次。

在嵌套循环里面,我们将检查该值是否大于我们要检查的数字。然后,让我们把我们的nums_list 的i ,我们将更新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 的平方,而空间复杂度将是o 的n 。

4

上面的解决方案已经足够了,但是另一种方法,n log ,使用二进制搜索到我们的临时数组的左边,使用bisect_left 。

from bisect import bisect_left
#Python小白学习交流群:153708845
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

热门相关:豪门蜜爱:独宠天后小萌妻   慕少,你老婆又重生了   重生成偏执霍少的小仙女   女大学生练歌厅   去里屋的出差男