Längste ansteigende Teilsequenz in Python

Wir werden lernen, was eine Teilfolge ist und wie man die am längsten ansteigende Teilfolge aus einem Array mit dem n-Quadrat-Ansatz und dem binären Suchansatz in Python berechnet.

Verwenden Sie den N-Quadrat-Ansatz, um die am längsten ansteigende Teilsequenz in Python zu berechnen

Eine berühmte Frage wird nach der am längsten wachsenden Unterfolge in der Python-Community gestellt und in verschiedenen Interviews gestellt. Es ist ein Leetcode-Problem, und die Frage lautet: Es wird ein unsortiertes Array von ganzen Zahlen gegeben und die Länge der längsten ansteigenden Teilfolge oder Teilmenge des gegebenen Arrays ermittelt.

Eine Teilmenge ist wie ein kurzes Array eines Arrays; Jedes Array könnte mehrere Teilmengen haben. Die andere Sache ist, dass Subarray einige der Elemente aus diesem [10,9,2,5,3,7,101,18]-Array sein würde, aber in einer kontinuierlichen Untersequenz.

Es kann wie [2, 3, 5, 7] sein, aber es kann nicht [2,3,101] sein, sodass die Sequenz nicht unterbrochen werden muss, wenn ein Subarray diskutiert wird. Und in der Folge muss die Reihenfolge, in der die Elemente im Array erscheinen, dieselbe sein, aber es könnte jedes der Individuen sein.

Wie wir sehen, lautet die Antwort in diesem Fall zum Beispiel [2, 3, 7,101]; die 5 ist nicht da, aber das ist ok, weil es eine Teilfolge ist.

Wenn wir die am längsten ansteigende Teilfolge von [10,9,2,5,3,7,101,18] sehen, finden wir [2, 5, 7, 101]; dies hätte auch eine Antwort bedeuten können, aber die Antwort könnte auch [2, 3, 7, 101] sein, das ist auch unsere andere Teilfolge. Das [3, 7, 101] ist auch eine Unterfolge, aber das ist nicht die längste, also werden wir es nicht berücksichtigen.

Es kann mehr als eine Kombination geben; Wie wir gerade gesehen haben, müssen wir nur die Länge zurückgeben.

Mit dem Beispiel könnten wir uns leicht eine rekursive Lösung vorstellen, die mit Null-Indizes beginnt und alle verschiedenen Pfade durchläuft. Mit diesem Array [0,3,1,6,2,2,7] könnten wir zum Beispiel mit 0 zu 3 gehen, oder wir können zu 1 gehen oder gehen Sie zu 6.

Und dann, von diesem Punkt an, rekursiv weitermachen. Schauen Sie sich das folgende Beispiel an, welcher Pfad der längste ist, der exponentiell sein wird; Wir können leicht denken, dass es einen dynamischen Programmieransatz geben muss.

Wir haben also ein Array und jeder dieser Indizes hat mindestens eine Länge.

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

Wir beginnen beim ersten Index, 0, dessen Länge 1 ist, aber bei 3 können wir nach hinten schauen und wenn 3 grösser als 0 ist, dann hat 3 2 Längen . Wenn wir wieder mit 1 gehen, schauen wir hinter alle Indizes vor dem aktuellen Index.

Anhand der Null-Indizes können wir sehen, dass 1 größer als 0 ist, aber 1 nicht größer als 3, also berechnen wir an dieser Stelle 0 und 1 und ihre Länge wäre 2.

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

Wenn wir 6 betrachten, schauen wir uns von Anfang an hinten an, wir wissen, dass 6 größer ist als [0,1] oder [0,3], und einschließlich 6 wäre seine Länge 3. dann ist auch die Länge von 2 gleich 3, und so weiter, das ist ein quadratischer Ansatz.

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

Zeitkomplexität und Raumkomplexität

Lassen Sie uns in den Code springen und unsere Klasse namens CalculateSubSequence erstellen; In der Funktion lengthOfLIS initialisieren wir unsere Variable nums_list mit der Länge von nums mit einem Array, das nur einmal sein wird.

Innerhalb der verschachtelten Schleifen prüfen wir, ob der Wert größer als die Zahl ist, die wir prüfen. Nehmen wir dann unsere nums_list von i, und wir aktualisieren den nums_list-Wert, während wir den Maximalwert mit nums_list[i] nehmen.

i kommt nach der Iteration von der äußeren Schleife, und für nums_list[j] kommt das j nach der Iteration von der inneren Schleife, dann fügen wir 1 damit hinzu. Am Ende geben wir den maximalen Wert von nums_list zurück.

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])

Hier ist die Zeitkomplexität n zum Quadrat, und die Raumkomplexität ist o von n.

4

Die obige Lösung ist ausreichend, aber ein anderer Ansatz, n log, verwendet eine binäre Suche auf der linken Seite unseres temporären Arrays mit 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])

Ausgang:

4