如何使用Python中的N平方法和二進制搜索法計算一個數(shù)組中最長的遞增子序列。

使用N平方法計算最長的遞增子序列

在Python社區(qū)中，有一個著名的問題是關于最長遞增子序列的，在不同的面試中也會被問到。這是一個Leetcode ，問題說：給定一個未排序的整數(shù)數(shù)組，找出該數(shù)組的最長遞增子序列或子集的長度。

一個子集就像一個數(shù)組的短數(shù)組；每個數(shù)組可以有多個子集。另一件事是子數(shù)組將是這個[10,9,2,5,3,7,101,18] 數(shù)組中的一些元素，但以連續(xù)的子序列方式。

它可以像[2, 3, 5, 7] ，但不能像[2,3,101] ，所以在討論子數(shù)組時不需要打破順序。而且，在子序列中，元素在數(shù)組中出現(xiàn)的順序必須是相同的，但可以是任何一個個體。

例如，在這種情況下，我們可以看到，答案是[2, 3, 7,101] ；5 ，但這是可以的，因為它是一個子序列。

如果我們看到從[10,9,2,5,3,7,101,18] 開始的最長的遞增子序列，我們會發(fā)現(xiàn)[2, 5, 7, 101] ；這也可能意味著一個答案，但答案也可能是[2, 3, 7, 101] ，這也是我們的另一個子序列。[3, 7, 101] 也是一個子序列，但這不是最長的，所以我們不考慮它。

可能有不止一個組合；正如我們剛剛看到的，我們只需要返回長度。

通過這個例子，我們可以很容易地想到一個遞歸的解決方案，從零索引開始，沿著所有不同的路徑進行。使用這個數(shù)組[0,3,1,6,2,2,7] ，我們可以采取，例如，用0 ，我們可以轉(zhuǎn)到3 ，或者我們可以轉(zhuǎn)到1 ，或者轉(zhuǎn)到6 。

然后，從這一點開始，遞歸地繼續(xù)下去?？纯聪旅娴睦?，哪條路徑最長，會是指數(shù)級的；我們很容易想到必須要有一些動態(tài)編程的方法。

所以，我們有一個數(shù)組，每個索引至少有一個長度。

[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,...]

時間復雜度和空間復雜度

讓我們跳入代碼，創(chuàng)建我們的類，稱為CalculateSubSequence ；在lengthOfLIS 函數(shù)里面，我們初始化我們的nums_list 變量為nums 的長度，這個數(shù)組將只有1次。

在嵌套循環(huán)里面，我們將檢查該值是否大于我們要檢查的數(shù)字。然后，讓我們把我們的nums_list 的i ，我們將更新nums_list 的值，同時使用最大值 nums_list[i].

i 在外循環(huán)的迭代之后，對于 nums_list[j],j 是在內(nèi)循環(huán)迭代后產(chǎn)生的，然后我們將其添加到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

上面的解決方案已經(jīng)足夠了，但是另一種方法，n log ，使用二進制搜索到我們的臨時數(shù)組的左邊，使用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])

輸出：文章來源地址http://www.zghlxwxcb.cn/news/detail-712138.html

4

到了這里，關于Python中最長的遞增序列的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！