Find Pivot Index

+10

Ti viene fornito un array di numeri interi nums. Un indice pivot è un indice in cui la somma dei valori alla sua sinistra è uguale alla somma dei valori alla sua destra. Il valore dell'indice pivot non appartiene a nessuno dei due lati e un lato senza valori ha somma pari a 0.

Restituisci l'indice pivot più a sinistra oppure -1 se nessun indice è un pivot.

Funzione

pivotIndex(nums: integer-array) → integer

numsinteger-array: l'array di interi da bilanciare
Restituisceinteger: l'indice del pivot più a sinistra, oppure -1 se non ce n'è nessuno

Vincoli

1 ≤ nums.length ≤ 10⁴
-1000 ≤ nums[i] ≤ 1000

Esempi

Input: nums = [3, 1, 5, 2, 2]
Output: 2
Spiegazione: All'indice 2 il lato sinistro è 3 + 1 = 4 e il lato destro è 2 + 2 = 4. L'indice 0 e l'indice 1 non sono in equilibrio (sinistra 0 contro 10, sinistra 3 contro 9), quindi 2 è il pivot più a sinistra.

Input: nums = [1, 2, 3]
Output: -1
Spiegazione: I tre candidati danno 0 contro 5, 1 contro 3 e 3 contro 0. Nessun indice è in equilibrio, quindi la risposta è -1.

+17 test nascosti all’invio

Per approfondire

Riesci a trovare il pivot più a sinistra leggendo ogni valore una sola volta, senza prima sommare il totale? Quanto costa in termini di memoria?

Suggerimenti

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

0 di 3 aperti

Soluzione

Controllare un indice richiede due somme, ma ricalcolarle a ogni indice fa crescere il lavoro con il quadrato della lunghezza. La soluzione è smettere di ricalcolarle: la somma a sinistra cresce di un valore a ogni passaggio, e la somma a destra è ciò che resta del totale. Una passata per calcolare il totale e una seconda passata con una somma progressiva a sinistra individuano il perno più a sinistra, usando due numeri in memoria.

Somma entrambi i lati a ogni indice

Corretto, ma non termina sui test più grandi

Intuizione

Segui la definizione. Per ogni indice i, somma i valori che lo precedono, somma i valori che lo seguono e confronta i risultati. Il primo indice in cui le due somme coincidono è la risposta, perché provi gli indici da sinistra a destra.

I bordi si gestiscono da soli. All’indice 0 il ciclo a sinistra viene eseguito zero volte, quindi la somma a sinistra è 0; all’ultimo indice il ciclo a destra viene eseguito zero volte. Ecco perché [4, -4, 9] restituisce 2.

Il problema è il costo. Per ogni indice si sommano gli altri n-1 valori, quindi il lavoro totale è di circa n² addizioni. Con 10.000 valori si arriva a quasi 100 milioni di addizioni, e la maggior parte ripete somme che avevi già calcolato un indice prima.

Algoritmo

Fai scorrere i su ogni indice di nums.
Somma nums[0] fino a nums[i-1] come somma a sinistra.
Somma nums[i+1] fino all'ultimo valore come somma a destra.
Se le due somme sono uguali, restituisci i.
Se nessun indice corrisponde, restituisci -1.

def pivotIndex(nums):
    n = len(nums)
    for i in range(n):
        left = 0
        for j in range(i):
            left += nums[j]
        right = 0
        for j in range(i + 1, n):
            right += nums[j]
        if left == right:
            return i
    return -1

Array delle somme prefisse

Intuizione

La soluzione per forza bruta continua a sommare i segmenti dell’array. Un array delle somme prefisse esegue questo lavoro una sola volta. Sia prefix[k] la somma dei primi k valori, con prefix[0] = 0. Per [3, 1, 5, 2, 2] è [0, 3, 4, 9, 11, 13].

Ora ogni segmento è la differenza tra due elementi. La parte a sinistra dell’indice i è costituita dai primi i valori, quindi è prefix[i]. La parte a destra è tutto ciò che viene dopo nums[i], ovvero prefix[n] - prefix[i+1]. All’indice 2 si ottiene 4 a sinistra e 13 - 9 = 4 a destra: è un pivot.

Costruire l’array richiede un solo passaggio e ogni controllo richiede tempo costante, quindi la ricerca completa è O(n). Il costo è n+1 numeri aggiuntivi in memoria.

Algoritmo

Crea prefix di lunghezza n+1 con prefix[0] = 0.
Compilalo: prefix[k+1] = prefix[k] + nums[k].
Per ogni indice i, leggi la somma a sinistra come prefix[i] e la somma a destra come prefix[n] - prefix[i+1].
Restituisci il primo i per cui sono uguali, oppure -1 dopo il ciclo.

def pivotIndex(nums):
    n = len(nums)
    # prefix[k] is the sum of the first k values.
    prefix = [0] * (n + 1)
    for k in range(n):
        prefix[k + 1] = prefix[k] + nums[k]
    for i in range(n):
        left = prefix[i]
        right = prefix[n] - prefix[i + 1]
        if left == right:
            return i
    return -1

Somma totale e somma progressiva a sinistra

Intuizione

Osserva quali voci del prefisso legge l’approccio precedente. All’indice i servono prefix[i], prefix[i+1] e prefix[n]. L’ultimo è il totale, che non cambia mai, mentre gli altri due sono la somma progressiva che otterresti percorrendo l’array una volta. Quindi puoi mantenere il totale e una sola somma progressiva a sinistra, invece dell’intero array.

Ogni valore si trova a sinistra, sul pivot oppure a destra. Quindi la somma a destra è il totale meno la somma a sinistra meno nums[i]. Per [3, 1, 5, 2, 2] il totale è 13. All’indice 0 la somma a sinistra è 0 e quella a destra è 13 - 0 - 3 = 10. All’indice 1 è 3 contro 9. All’indice 2 è 4 contro 13 - 4 - 5 = 4, quindi restituisci 2.

L’ordine all’interno del ciclo è importante. Confronta prima, poi aggiungi nums[i] alla somma a sinistra, così la somma a sinistra non include mai il valore dell’indice che stai verificando. Restituire il risultato alla prima corrispondenza dà il pivot più a sinistra.

Leggi l’array due volte, una per il totale e una per la scansione, quindi il tempo è O(n). Vengono memorizzati solo due numeri, quindi lo spazio aggiuntivo è O(1).

Algoritmo

Aggiungi ogni valore a total.
Imposta left su 0.
Per ogni indice i, se left è uguale a total - left - nums[i], restituisci i.
Altrimenti aggiungi nums[i] a left e prosegui.
Se il ciclo termina, restituisci -1.

def pivotIndex(nums):
    total = sum(nums)
    left = 0
    for i, value in enumerate(nums):
        # Everything that is not on the left and not nums[i] is on the right.
        if left == total - left - value:
            return i
        left += value
    return -1

Trappole e casi limite

La maggior parte delle risposte sbagliate mette il valore del pivot stesso da un lato oppure salta l'indice di un bordo.

Aggiungere nums[i] alla somma sinistra prima del confronto. Il lato sinistro include quindi il valore del pivot e [3, 1, 5, 2, 2] non trova più l'indice 2.
Calcolare il lato destro come total - left. Così nums[i] viene conteggiato anche a destra; sottrai anche quel valore.
Saltare l'indice 0 o l'ultimo indice. Entrambi possono essere il pivot, perché la somma di un lato vuoto è 0. [1, -1, 1] restituisce 0 e [4, -4, 9] restituisce 2.
Restituire l'ultima corrispondenza invece della prima. In [0, 0, 0] ogni indice è bilanciato e la risposta è 0.
Usare due puntatori che si spostano verso l'interno da entrambe le estremità e aumentare il lato più piccolo. Funziona solo quando tutti i valori sono non negativi; qui i valori scendono fino a -1000, quindi un lato può ridursi mentre cresce.
Dimenticare che gli array di Lua e R iniziano da 1. Restituisci i-1 per ottenere un indice a partire da 0.

Domande frequenti4

Qual è la complessità temporale di Find Pivot Index?

La soluzione con il totale e la somma progressiva richiede un tempo O(n): una passata per sommare l'array e una passata per scorrerlo. Usa uno spazio aggiuntivo O(1). Ricalcolare entrambi i lati a ogni indice richiede invece un tempo O(n²).

Perché la somma a destra è uguale al totale meno la somma a sinistra meno nums[i]?

Ogni valore dell'array si trova esattamente in una di tre posizioni: a sinistra di i, in corrispondenza di i o a destra di i. Le loro somme danno il totale, quindi la somma a destra è il totale meno le altre due parti. Questo ti permette di controllare un indice senza dover mai sommare gli elementi a destra.

È possibile risolvere «Trova l'indice pivot» con due puntatori?

Non in modo affidabile. Una scansione con due puntatori che espande sempre il lato più piccolo presuppone che aggiungere un valore renda un lato più grande, ma questo non vale quando i valori possono essere negativi: un lato può ridursi mentre lo espandi, quindi la scansione può spostare un puntatore oltre il vero punto di divisione. Il metodo della somma progressiva non fa supposizioni sui segni e controlla ogni indice.

Qual è l’indice pivot di un array con un solo elemento?

È 0. Entrambi i lati dell'unico elemento sono vuoti e un lato vuoto ha somma pari a 0, quindi i due lati sono uguali. La soluzione con la somma progressiva restituisce 0 al primo confronto: il lato sinistro è 0 e anche il totale meno 0 meno il valore è 0.

Python

def pivotIndex(nums):
    # Scrivi il codice qui

Casi di test

Caso 1

Caso 2

Caso 3

Input

nums = [3, 1, 5, 2, 2]

Atteso

Find Pivot Index

Funzione

Vincoli

Esempi

Suggerimenti

Soluzione

Somma entrambi i lati a ogni indice

Array delle somme prefisse

Somma totale e somma progressiva a sinistra

Trappole e casi limite

Domande frequenti4

Problemi simili