翼度科技»论坛 编程开发 python 查看内容

Python中最长的递增序列

4

主题

4

帖子

12

积分

新手上路

Rank: 1

积分
12
如何使用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 。
然后,从这一点开始,递归地继续下去。看看下面的例子,哪条路径最长,会是指数级的;我们很容易想到必须要有一些动态编程的方法。
所以,我们有一个数组,每个索引至少有一个长度。
  1. [0,3,1,6,2,2,7]
  2. [1,1,1,1,1,1,1]
复制代码
我们将从第一个索引开始,0 ,其长度是1 ,但有了3 ,我们可以看后面,如果3 大于0 ,那么3 有2 的长度。如果我们再以1 ,我们将在当前索引之前的所有索引后面寻找。
从零索引中,我们可以看到1 大于0 ,但1 不大于3 ,所以在这一点上,我们要计算0 和1 ,其长度将是2 。
  1. [0,3,1,6,2,2,7]
  2. [1,2,2,1,1,1,1]
复制代码
在考虑6 ,让我们从后面开始看,我们知道6 大于[0,1] 或[0,3] ,包括6 ,其长度将是3 ,然后也是2 的长度是3 ,以此类推,这是一个平方的方法。
  1. [0,3,1,6,2,2,7]
  2. [1,2,2,3,3,...]
复制代码
时间复杂度和空间复杂度

让我们跳入代码,创建我们的类,称为CalculateSubSequence ;在lengthOfLIS 函数里面,我们初始化我们的nums_list 变量为nums 的长度,这个数组将只有1次。
在嵌套循环里面,我们将检查该值是否大于我们要检查的数字。然后,让我们把我们的nums_list 的i ,我们将更新nums_list 的值,同时使用最大值 nums_list.
i 在外循环的迭代之后,对于 nums_list[j],j 是在内循环迭代后产生的,然后我们将其添加到1 中。最后,我们将返回nums_list 的最大值。
  1. class CalculateSubSequence:
  2.     def lengthOfLIS(self, nums: list[int]) -> int:
  3.         nums_list = [1] * len(nums)
  4.         for i in range(len(nums)-1, -1, -1):
  5.             for j in range(i+1, len(nums)):
  6.                 if nums[i] < nums[j]:
  7.                     nums_list[i] = max(nums_list[i], nums_list[j] + 1)
  8.         return max(nums_list)
  9. sbs = CalculateSubSequence()
  10. sbs.lengthOfLIS([0,3,1,6,2,2,7])
复制代码
这里的时间复杂度将是n 的平方,而空间复杂度将是o 的n 。
  1. 4
复制代码
上面的解决方案已经足够了,但是另一种方法,n log ,使用二进制搜索到我们的临时数组的左边,使用bisect_left 。
  1. from bisect import bisect_left
  2. #Python小白学习交流群:153708845
  3. class CalculateSubSequence:
  4.     def lengthOfLIS(self, nums: list[int]) -> int:
  5.         n= len(nums)
  6.         tmp=[nums[0]]
  7.         for n in nums:
  8.             x = bisect_left(tmp,n)
  9.             if x ==len(tmp):
  10.                 tmp.append(n)
  11.             elif tmp[x]>n:
  12.                 tmp[x]=n
  13.         return len(tmp)
  14. sbs = CalculateSubSequence()
  15. sbs.lengthOfLIS([0,3,1,6,2,2,7])
复制代码
输出:
  1. 4
复制代码
来源:https://www.cnblogs.com/xxpythonxx/p/17717656.html
免责声明:由于采集信息均来自互联网,如果侵犯了您的权益,请联系我们【E-Mail:cb@itdo.tech】 我们会及时删除侵权内容,谢谢合作!

举报 回复 使用道具