Product of Array Except Self

Q: Warum ist Division bei „Product of Array Except Self“ nicht erlaubt?

Das Teilen des Gesamtprodukts durch nums[i] funktioniert nicht, wenn das Array eine Null enthält, da das Gesamtprodukt dann 0 ist und am Index der Null selbst durch 0 geteilt werden müsste. Damit es funktioniert, müsste man die Nullen zählen und Sonderfälle behandeln. Die Regel führt dich zu Präfix- und Suffixprodukten, die Nullen ganz ohne Sonderfälle behandeln.

MittelPräfixsummen

+10

Du erhältst ein Array aus ganzen Zahlen nums. Gib ein Array answer derselben Länge zurück, wobei answer[i] das Produkt aller Elemente von nums außer dem am Index i ist. Führe dies in O(n)-Zeit und ohne Division aus.

Funktion

productExceptSelf(nums: integer-array) → integer-array

numsinteger-array: das Array von Ganzzahlen mit mindestens zwei Elementen
Gibt zurückinteger-array: ein Array, dessen Wert am Index i das Produkt aller Elemente außer nums[i] ist

Einschränkungen

2 ≤ nums.length ≤ 10⁴
-30 ≤ nums[i] ≤ 30
Das Produkt aller Werte ungleich null in nums passt in eine vorzeichenbehaftete 32-Bit-Ganzzahl, daher passt auch jedes Produkt, das du auf dem Weg bildest.

Beispiele

Eingabe: nums = [2, 3, 4, 5]
Ausgabe: [60, 40, 30, 24]
Erklärung: Wenn man die 2 weglässt, bleiben 3 × 4 × 5 = 60, und wenn man die 5 weglässt, bleiben 2 × 3 × 4 = 24. Bei den beiden mittleren funktioniert es genauso: 2 × 4 × 5 = 40 und 2 × 3 × 5 = 30.

+14 versteckte Tests beim Einreichen

Weiterführende Frage

Kannst du nur zusätzlichen Speicherplatz von O(1) verwenden, ohne das Array mitzuzählen, das du zurückgibst?

Tipps

Öffne sie nacheinander. Jeder verrät ein bisschen mehr.

0 von 3 geöffnet

Lösung

Das Produkt aller Werte außer nums[i] ist das Produkt der Werte links davon multipliziert mit dem Produkt der Werte rechts davon. Das Gesamtprodukt durch nums[i] zu teilen, sieht kürzer aus, ist hier aber nicht erlaubt und funktioniert bei Nullen nicht, denn dann ist das Gesamtprodukt 0. Mit Präfix- und Suffixprodukten erhält man in zwei Durchläufen alle Produkte links und rechts, sodass die Berechnung der Antwort O(n) Zeit benötigt. Das Ausgabe-Array kann die linken Produkte aufnehmen, und eine Variable speichert das rechte Produkt, sodass kein weiteres Array benötigt wird.

Multipliziere die anderen für jeden Index

Korrekt, wird aber bei den größten Tests nicht fertig

Idee

Folge der Definition. Beginne für jeden Index i ein Produkt bei 1 und multipliziere jeden Wert nums[j] hinein, dessen Index j nicht i ist. Diesen Index zu überspringen, statt ihn später herauszudividieren, sorgt dafür, dass Nullen keine Probleme verursachen: In [-2, 5, 0, 3] kommt das Produkt für Index 2 nie mit der 0 in Berührung und ergibt -30.

Das ist korrekt, wiederholt aber unnötig Arbeit. Die Produkte für Index 0 und Index 1 haben bis auf zwei Werte alle gemeinsam, und trotzdem multiplizierst du sie alle noch einmal. Für jede der n Positionen sind n-1 Multiplikationen nötig, insgesamt also etwa 10^8, wenn n = 10^4. C schafft das in einem Bruchteil einer Sekunde, aber Python, Ruby oder R brauchen viel zu lange.

Algorithmus

Erstelle ein Antwort-Array der Länge n.
Setze für jeden Index i product auf 1.
Multipliziere product mit jedem nums[j], dessen Index j nicht i ist.
Speichere product am Index i der Antwort.
Gib die Antwort zurück.

def productExceptSelf(nums):
    n = len(nums)
    answer = []
    for i in range(n):
        product = 1
        for j in range(n):
            if j != i:
                product *= nums[j]
        answer.append(product)
    return answer

Präfix- und Suffix-Produktarrays

Idee

Teile das Produkt für den Index i in zwei Teile auf: die Werte vor i und die Werte danach. Nenne diese Produkte before[i] und after[i]. Dann gilt answer[i] = before[i] × after[i], und nums[i] bleibt ohne Division unberücksichtigt.

Jedes Array wächst mit einer Multiplikation ausgehend von seinem Nachbarn. before[0] ist 1, das Produkt aus keinen Werten, und before[i] = before[i-1] × nums[i-1]. Vom anderen Ende aus ist after[n-1] gleich 1 und after[i] = after[i+1] × nums[i+1]. Für [2, 3, 4, 5] erhältst du before = [1, 2, 6, 24] und after = [60, 20, 5, 1]. Multiplizierst du sie positionsweise, ergibt sich [60, 40, 30, 24].

Drei Durchläufe mit jeweils n Schritten ergeben eine Laufzeit von O(n). Die beiden Hilfsarrays benötigen zusätzlich O(n) Speicher, den der nächste Ansatz einspart.

Algorithmus

Fülle before von links aus: before[0] = 1, danach ist jeder Eintrag das Produkt aus dem vorherigen Eintrag und dem vorherigen Wert.
Fülle after von rechts aus: after[n-1] = 1, danach ist jeder Eintrag das Produkt aus dem nächsten Eintrag und dem nächsten Wert.
Setze answer[i] für jeden Index auf before[i] × after[i].
Gib answer zurück.

def productExceptSelf(nums):
    n = len(nums)
    # before[i] = product of nums[0..i-1], after[i] = product of nums[i+1..n-1]
    before = [1] * n
    after = [1] * n
    for i in range(1, n):
        before[i] = before[i - 1] * nums[i - 1]
    for i in range(n - 2, -1, -1):
        after[i] = after[i + 1] * nums[i + 1]
    return [before[i] * after[i] for i in range(n)]

Linke Produkte in der Antwort, ein laufendes rechtes Produkt

Idee

Du benötigst nie das gesamte after-Array auf einmal. Wenn du vom rechten Ende ausgehst, ist das Produkt der Werte rechts von i eine einzelne Zahl. Speichere sie in einer Variablen right und aktualisiere sie in jedem Schritt mit einer Multiplikation.

Schreibe die linken Produkte also in einem ersten Durchlauf direkt in das Antwort-Array. Multipliziere in einem zweiten Durchlauf von rechts answer[i] mit right und multipliziere erst danach right mit nums[i]. Die Reihenfolge ist wichtig: Wenn du right am Index i verwendest, darf es nums[i] noch nicht enthalten.

Bei [2, 3, 4, 5] ergibt der erste Durchlauf [1, 2, 6, 24]. Im zweiten Durchlauf verwendet right an den Indizes 3, 2, 1, 0 die Werte 1, 5, 20, 60 und wandelt das Array in [60, 40, 30, 24] um. Die Laufzeit beträgt weiterhin O(n), und zusätzlich zum zurückgegebenen Array benötigst du als zusätzlichen Speicher nur eine Variable: O(1).

Algorithmus

Setze answer[0] = 1 und setze dann von links nach rechts answer[i] = answer[i-1] × nums[i-1].
Setze right auf 1.
Multipliziere vom letzten Index rückwärts bis 0 answer[i] mit right.
Multipliziere anschließend right mit nums[i].
Gib answer zurück.

def productExceptSelf(nums):
    n = len(nums)
    # Pass 1: answer[i] = product of everything left of i
    answer = [1] * n
    for i in range(1, n):
        answer[i] = answer[i - 1] * nums[i - 1]
    # Pass 2: multiply in the product of everything right of i
    right = 1
    for i in range(n - 1, -1, -1):
        answer[i] *= right
        right *= nums[i]
    return answer

Stolperfallen und Grenzfälle

Die Fehler entstehen hier durch Nullen, durch die Reihenfolge der beiden Aktualisierungen im zweiten Durchlauf und durch die Ränder des Arrays.

Das Teilen des Gesamtprodukts durch nums[i] schlägt fehl, sobald eine 0 vorkommt. Für [-2, 5, 0, 3] ist das Gesamtprodukt 0, und bei Index 2 müsste man 0 durch 0 teilen. Das Zählen der Nullen kann Abhilfe schaffen, aber Division ist in der Aufgabenstellung ohnehin ausgeschlossen.
Wenn du right mit nums[i] multiplizierst, bevor du es verwendest, fließt nums[i] in sein eigenes Produkt ein. Bei [2, 3, 4, 5] wird der letzte Wert zu 120 statt zu 24.
Die linken Produkte mit nums[0] statt mit 1 beginnen lassen. Links von Index 0 steht kein Wert, daher ist sein linkes Produkt das leere Produkt 1, und answer[0] wird zum Produkt ausschließlich der Werte rechts davon.
Schleifengrenzen: Der linke Durchlauf liest nums[i-1] und beginnt daher bei Index 1. Ein Suffix-Array liest nums[i+1] und beginnt daher bei Index n-2.
Zwei Nullen ergeben für jede Antwort den Wert 0. Bei einer Null ist jede Antwort 0, außer der an derselben Stelle wie die Null. Teste beide Fälle, bevor du deinem Code vertraust.

Häufige Fragen4

Wie hoch ist die Zeitkomplexität von Product of Array Except Self?

Die Präfix- und Suffixlösung benötigt O(n) Zeit: einen Durchlauf von links und einen von rechts. Wenn die linken Produkte im Ausgabe-Array und ein einzelnes laufendes rechtes Produkt gespeichert werden, benötigt sie zusätzlich zum Ausgabe-Array O(1) Speicherplatz. Das Multiplizieren aller übrigen Werte für jeden Index benötigt O(n²) Zeit.

Warum ist Division bei „Product of Array Except Self“ nicht erlaubt?

Das Teilen des Gesamtprodukts durch nums[i] funktioniert nicht, wenn das Array eine Null enthält, da das Gesamtprodukt dann 0 ist und am Index der Null selbst durch 0 geteilt werden müsste. Damit es funktioniert, müsste man die Nullen zählen und Sonderfälle behandeln. Die Regel führt dich zu Präfix- und Suffixprodukten, die Nullen ganz ohne Sonderfälle behandeln.

Zählt das Ausgabe-Array als zusätzlicher Speicherplatz?

Nein. Du musst das Ergebnis ohnehin zurückgeben, daher wird es nach der üblichen Konvention nicht zum Speicherplatzbedarf gezählt. Die linken Produkte darin zu speichern und das rechte Produkt in einer Variablen zu behalten, zählt daher als zusätzlicher Speicherplatz von O(1).

Wie behandelt Product of Array Except Self Nullen?

Bei Präfix- und Suffixprodukten benötigen Nullen keinen Sonderfall. Jedes Links- oder Rechtsprodukt, das über eine Null hinausgeht, ist 0, und das Produkt für den Index der Null selbst überspringt sie. Bei zwei oder mehr Nullen enthält jedes Produkt eine davon, sodass jede Antwort 0 ist.

Python

def productExceptSelf(nums):
    # Schreibe hier den Code

Testfälle

Fall 1

Fall 2

Fall 3

Eingabe

nums = [2, 3, 4, 5]

Erwartet

[60, 40, 30, 24]

Product of Array Except Self

Funktion

Einschränkungen

Beispiele

Tipps

Lösung

Multipliziere die anderen für jeden Index

Präfix- und Suffix-Produktarrays

Linke Produkte in der Antwort, ein laufendes rechtes Produkt

Stolperfallen und Grenzfälle

Häufige Fragen4

Ähnliche Aufgaben