Product of Array Except Self

Q: Perché la divisione non è consentita in «Prodotto dell’array escluso sé stesso»?

Dividere il prodotto totale per nums[i] non funziona quando l’array contiene uno zero, perché il totale è 0 e per l’indice dello zero stesso sarebbe necessaria una divisione per 0. Per farlo funzionare servono un conteggio degli zeri e dei casi speciali. La regola ti orienta verso i prodotti dei prefissi e dei suffissi, che gestiscono gli zeri senza alcun caso speciale.

MedioSomme prefisse

+10

Hai un array di numeri interi nums. Restituisci un array answer della stessa lunghezza, in cui answer[i] è il prodotto di ogni elemento di nums tranne quello all’indice i. Fallo in tempo O(n) e senza usare la divisione.

Funzione

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

numsinteger-array: l'array di numeri interi, con almeno due elementi
Restituisceinteger-array: un array il cui valore all'indice i è il prodotto di tutti gli elementi tranne nums[i]

Vincoli

2 ≤ nums.length ≤ 10⁴
-30 ≤ nums[i] ≤ 30
Il prodotto di tutti i valori diversi da zero in nums rientra in un intero con segno a 32 bit, quindi anche ogni prodotto che costruisci lungo il percorso vi rientra.

Esempi

Input: nums = [2, 3, 4, 5]
Output: [60, 40, 30, 24]
Spiegazione: Escludendo il 2 rimane 3 × 4 × 5 = 60, ed escludendo il 5 rimane 2 × 3 × 4 = 24. I due numeri centrali funzionano allo stesso modo: 2 × 4 × 5 = 40 e 2 × 3 × 5 = 30.

+14 test nascosti all’invio

Per approfondire

Puoi usare solo O(1) spazio aggiuntivo, senza contare l'array che restituisci?

Suggerimenti

Aprili uno alla volta. Ognuno rivela un po’ di più.

0 di 3 aperti

Soluzione

Il prodotto di tutto tranne nums[i] è il prodotto dei valori alla sua sinistra moltiplicato per il prodotto dei valori alla sua destra. Dividere il prodotto totale per nums[i] sembra più breve, ma qui non è consentito e non funziona in presenza di zeri, quando il prodotto totale è 0. I prodotti dei prefissi e dei suffissi forniscono tutti i prodotti a sinistra e a destra in due passaggi, quindi la risposta richiede un tempo di O(n). L’array di output può contenere i prodotti a sinistra e una variabile può contenere il prodotto a destra, quindi non serve nessun altro array.

Moltiplica gli altri per ogni indice

Corretto, ma non termina sui test più grandi

Intuizione

Segui la definizione. Per ogni indice i, inizia un prodotto da 1 e moltiplica ogni nums[j] il cui indice j non è i. Saltare quell’indice, invece di dividerlo in seguito, rende innocua la presenza di zeri: in [-2, 5, 0, 3] il prodotto per l’indice 2 non considera mai lo 0 e il risultato è -30.

È corretto, ma ripete il lavoro. I prodotti per l’indice 0 e l’indice 1 condividono tutti i valori tranne due, e li moltiplichi comunque di nuovo tutti. Ognuna delle n posizioni richiede n-1 moltiplicazioni, circa 10^8 in totale quando n = 10^4. C riesce a farlo in una frazione di secondo, ma Python, Ruby o R ci mettono troppo.

Algoritmo

Crea un array di risposte di lunghezza n.
Per ogni indice i, imposta product su 1.
Moltiplica product per ogni nums[j] il cui indice j non è i.
Memorizza product all'indice i della risposta.
Restituisci la risposta.

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

Array di prodotti di prefissi e suffissi

Intuizione

Dividi il prodotto per l’indice i in due parti: i valori prima di i e i valori dopo. Chiama questi prodotti before[i] e after[i]. Quindi answer[i] = before[i] × after[i] e nums[i] viene escluso senza eseguire alcuna divisione.

Ogni array cresce a partire dall’elemento vicino con una moltiplicazione. before[0] è 1, il prodotto di nessun valore, e before[i] = before[i-1] × nums[i-1]. Dall’altra estremità, after[n-1] è 1 e after[i] = after[i+1] × nums[i+1]. Per [2, 3, 4, 5] ottieni before = [1, 2, 6, 24] e after = [60, 20, 5, 1]; moltiplicandoli posizione per posizione ottieni [60, 40, 30, 24].

Tre passaggi di n operazioni richiedono tempo O(n). I due array di supporto richiedono O(n) di memoria aggiuntiva, che il prossimo approccio elimina.

Algoritmo

Riempi before da sinistra: before[0] = 1, poi ogni elemento è l'elemento precedente moltiplicato per il valore precedente.
Riempi after da destra: after[n-1] = 1, poi ogni elemento è l'elemento successivo moltiplicato per il valore successivo.
Imposta answer[i] su before[i] × after[i] per ogni indice.
Restituisci answer.

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

Prodotti a sinistra nella risposta, un prodotto a destra in esecuzione

Intuizione

Non hai mai bisogno dell’intero array after tutto in una volta. Procedendo dall’estremità destra, il prodotto dei valori a destra di i è un singolo numero. Conservalo in una variabile right e aggiornalo con una moltiplicazione per ogni passaggio.

Quindi scrivi direttamente i prodotti a sinistra nell’array di risposta in un primo passaggio. In un secondo passaggio da destra, moltiplica answer[i] per right e solo allora moltiplica right per nums[i]. L’ordine è importante: quando usi right all’indice i, non deve ancora includere nums[i].

Per [2, 3, 4, 5], il primo passaggio lascia [1, 2, 6, 24]. Il secondo passaggio usa right = 1, 5, 20, 60 agli indici 3, 2, 1, 0 e trasforma l’array in [60, 40, 30, 24]. Il tempo resta O(n) e, oltre all’array restituito, la memoria aggiuntiva è una variabile: O(1).

Algoritmo

Imposta answer[0] = 1, poi da sinistra a destra imposta answer[i] = answer[i-1] × nums[i-1].
Imposta right a 1.
Dall'ultimo indice fino a 0, moltiplica answer[i] per right.
Poi moltiplica right per nums[i].
Restituisci answer.

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

Trappole e casi limite

Gli errori qui dipendono dagli zeri, dall’ordine dei due aggiornamenti nel secondo passaggio e dai limiti dell’array.

Dividere il prodotto totale per nums[i] non funziona quando compare uno 0. Per [-2, 5, 0, 3] il totale è 0 e all’indice 2 servirebbe dividere 0 per 0. Contare gli zeri può risolvere il problema, ma le regole vietano comunque la divisione.
Moltiplicare right per nums[i] prima di usarlo inserisce nums[i] nel suo stesso prodotto. Per [2, 3, 4, 5] l’ultimo valore diventa 120 invece di 24.
Iniziare i prodotti a sinistra da nums[0] invece che da 1. A sinistra dell’indice 0 non c’è nulla, quindi il suo prodotto è il prodotto vuoto, 1, e answer[0] finisce per essere solo il prodotto dei valori alla sua destra.
Limiti dei cicli: il passaggio a sinistra legge nums[i-1], quindi inizia all’indice 1. Un array dei suffissi legge nums[i+1], quindi inizia all’indice n-2.
Due zeri rendono ogni risposta 0. Un solo zero rende ogni risposta 0, tranne quella all’indice dello zero stesso. Verifica entrambi i casi prima di fidarti del tuo codice.

Domande frequenti4

Qual è la complessità temporale di Product of Array Except Self?

La soluzione con prefisso e suffisso richiede un tempo O(n): una passata da sinistra e una da destra. Con i prodotti a sinistra memorizzati nell'array di output e un unico prodotto progressivo a destra, richiede O(1) spazio aggiuntivo oltre all'output. Moltiplicare tutti gli altri valori per ogni indice richiede un tempo O(n²).

Perché la divisione non è consentita in «Prodotto dell’array escluso sé stesso»?

Dividere il prodotto totale per nums[i] non funziona quando l’array contiene uno zero, perché il totale è 0 e per l’indice dello zero stesso sarebbe necessaria una divisione per 0. Per farlo funzionare servono un conteggio degli zeri e dei casi speciali. La regola ti orienta verso i prodotti dei prefissi e dei suffissi, che gestiscono gli zeri senza alcun caso speciale.

La matrice di output conta come spazio aggiuntivo?

No. Devi comunque restituire la risposta, quindi di solito non la si considera nel conteggio dello spazio. Memorizzare i prodotti a sinistra al suo interno e mantenere il prodotto a destra in una variabile conta quindi come spazio aggiuntivo O(1).

Come gestisce Product of Array Except Self gli zeri?

Con i prodotti di prefisso e suffisso, gli zeri non richiedono casi speciali. Qualsiasi prodotto a sinistra o a destra che supera uno zero è 0, mentre il prodotto per l’indice dello zero stesso lo salta. Con due o più zeri, ogni prodotto ne contiene uno, quindi ogni risultato è 0.

Python

def productExceptSelf(nums):
    # Scrivi il codice qui

Casi di test

Caso 1

Caso 2

Caso 3

Input

nums = [2, 3, 4, 5]

Atteso

[60, 40, 30, 24]

Product of Array Except Self

Funzione

Vincoli

Esempi

Suggerimenti

Soluzione

Moltiplica gli altri per ogni indice

Array di prodotti di prefissi e suffissi

Prodotti a sinistra nella risposta, un prodotto a destra in esecuzione

Trappole e casi limite

Domande frequenti4

Problemi simili