Missing Number

FacileManipolazione dei bit Matematica e simulazione

+10

Ti viene fornita una lista nums di n interi distinti, ciascuno compreso tra 0 e n. L'intervallo da 0 a n contiene n+1 numeri, quindi esattamente uno di essi non è presente nella lista. Restituisci il numero mancante.

Funzione

missingNumber(nums: integer-array) → integer

numsinteger-array: n interi distinti dell’intervallo da 0 a n, in qualsiasi ordine
Restituisceinteger: l'unico numero da 0 a n che non è in nums

Vincoli

n == nums.length
1 ≤ n ≤ 10⁴
0 ≤ nums[i] ≤ n
Tutti i valori in nums sono distinti.

Esempi

Input: nums = [4, 2, 0, 1]
Output: 3
Spiegazione: L'elenco contiene 4 valori, quindi l'intervallo va da 0 a 4. Contiene 0, 1, 2 e 4, e 3 è l'unico numero senza corrispondenza.

+13 test nascosti all’invio

Per approfondire

Se l'elenco fosse ordinato, riusciresti a trovare il numero mancante in O(log n) usando la ricerca binaria?

Suggerimenti

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

0 di 3 aperti

Soluzione

Sai esattamente cosa dovrebbe contenere la lista: ogni numero intero da 0 a n. Cercare questi numeri uno per uno funziona, ma ripete una scansione completa per ogni numero. Invece, comprimi l’intero intervallo e la lista in un unico valore riassuntivo ciascuno, la somma o lo XOR, e la differenza tra i due è il numero mancante. Ciò richiede un solo passaggio e nessuna memoria aggiuntiva.

Controlla ogni candidato

Corretto, ma non termina sui test più grandi

Intuizione

La risposta è uno dei n+1 numeri da 0 a n. Prendili in ordine e scorri la lista cercando ciascuno di essi. Il primo candidato che non corrisponde a nessun valore è il numero mancante.

Questo è corretto perché ogni numero nell’intervallo si trova nella lista oppure è la risposta, e la lista non contiene duplicati, quindi la ricerca non trova esattamente uno dei candidati.

È lento perché ogni candidato richiede una scansione di fino a n valori. Quando il valore mancante è vicino alla fine, si cerca quasi ogni candidato: con n = 10^4 e il valore mancante vicino alla fine, si effettuano circa 5 × 10^7 confronti. Raddoppiando la lista, il lavoro quadruplica.

Algoritmo

Fai scorrere candidate da 0 fino a n, inclusi.
Esamina nums alla ricerca di un valore uguale a candidate.
Se la scansione lo trova, passa al candidato successivo.
Se la scansione termina senza trovare corrispondenze, restituisci candidate.

def missingNumber(nums):
    n = len(nums)
    for candidate in range(n + 1):
        # "in" on a list scans it from the start: O(n) per candidate.
        if candidate not in nums:
            return candidate
    return -1

Sottrai la somma dalla somma prevista

Intuizione

Se non mancasse nulla, la lista conterrebbe tutti i numeri da 0 a n, e la loro somma sarebbe n(n+1)/2. La lista reale è l'insieme completo a cui è stato tolto un numero, quindi la sua somma è inferiore esattamente di quel numero.

Per [4, 2, 0, 1], n è 4 e la somma dell'intervallo completo è 4 × 5 / 2 = 10. La somma della lista è 7 e 10 meno 7 fa 3.

Un'unica passata somma gli elementi della lista, quindi il tempo è O(n) e si mantiene un solo totale progressivo. Qui la somma completa è al massimo circa 5 × 10^7, un valore che rientra in un intero a 32 bit. Per valori di n molto più grandi, la formula va in overflow con un int a 32 bit, quindi le versioni Java, C, C++, C# e Rust eseguono i calcoli a 64 bit.

Algoritmo

Sia n la lunghezza di nums.
Calcola la somma totale n(n+1)/2.
Somma tutti i valori in nums.
Restituisci la somma totale meno la somma della lista.

def missingNumber(nums):
    n = len(nums)
    expected = n * (n + 1) // 2
    return expected - sum(nums)

Applica XOR agli indici con i valori

Intuizione

XOR annulla le coppie. a ^ a è 0, a ^ 0 è a e l’ordine delle operazioni non importa. Quindi, se fai XOR su un insieme di numeri in cui ogni elemento compare due volte, tranne un valore, le coppie si annullano e quel valore è ciò che rimane.

Costruisci un insieme del genere a partire dal problema: gli indici da 0 a n più i valori in nums. Un numero presente nell’elenco compare una volta come indice e una volta come valore, quindi si annulla. Il numero mancante compare solo come indice, quindi rimane. Il ciclo visita gli indici da 0 a n-1, quindi inizializza il risultato a n per includere l’ultimo.

Per [4, 2, 0, 1]: parti da 4, poi fai XOR con 0 e 4, 1 e 2, 2 e 0, 3 e 1. I 4, i 2, gli 1 e gli 0 si annullano tutti, e rimane 3. È un unico passaggio con un solo valore aggiornato man mano e, a differenza della somma, non supera mai i bit già usati da n, quindi non può andare in overflow.

Algoritmo

Imposta result su n, la lunghezza di nums.
Per ogni indice i, esegui lo XOR di result con i e con nums[i].
Restituisci result.

def missingNumber(nums):
    # Start with n, the one index the loop below never reaches.
    result = len(nums)
    for i, value in enumerate(nums):
        result ^= i ^ value
    return result

Trappole e casi limite

La maggior parte delle risposte errate deriva dai due estremi dell'intervallo.

Dimenticare che anche n può essere mancante. In [0, 1, 2] la risposta è 3, che non è un indice della lista. La versione con XOR deve iniziare da n, e una scansione ordinata che cerca il primo nums[i] != i deve restituire n quando tutte le posizioni corrispondono.
Usare la dimensione dell'intervallo sbagliata. I numeri vanno da 0 a n, cioè sono n+1 numeri, quindi la somma totale è n(n+1)/2, non (n-1)n/2.
Supporre che 0 sia sempre presente. In [1] la risposta è 0, e il codice che inizia la ricerca da 1 non lo trova.
Overflow nella versione con la somma. Con l'aritmetica a 32 bit, il prodotto n(n+1) va in overflow quando n supera circa 46.000, prima che la divisione per 2 possa essere d'aiuto, e n(n+1)/2 smette di rientrare nel limite intorno a 65.000. Usa l'aritmetica a 64 bit oppure XOR.

Domande frequenti4

Qual è la complessità temporale di Missing Number?

Le soluzioni con la somma e con XOR richiedono entrambe un tempo O(n) e uno spazio aggiuntivo O(1), perché leggono ogni valore una sola volta e mantengono un numero. Cercare nella lista ogni possibile candidato richiede O(n²). Ordinare prima e cercare l'intervallo mancante richiede O(n log n).

Perché XOR trova il numero mancante?

Eseguire XOR di un numero con se stesso dà 0, eseguire XOR con 0 non cambia nulla e l’ordine non conta. Quando esegui XOR tra tutti gli indici da 0 a n e tutti i valori, ogni numero presente nell’elenco compare due volte e si annulla. Il numero mancante compare una sola volta, come indice, quindi è il risultato.

Dovresti usare la formula della somma o XOR?

Entrambi richiedono un solo passaggio e memoria costante. La somma è più facile da spiegare, ma nell’aritmetica a 32 bit il prodotto n(n+1) va in overflow quando n supera circa 46.000, quindi serve l’aritmetica a 64 bit. XOR non va mai in overflow. In Python, Ruby e altri linguaggi con interi illimitati, la differenza scompare.

Riesci a risolvere Missing Number con un insieme hash?

Sì. Inserisci tutti i valori in un insieme, poi controlla da 0 a n e restituisci il primo numero che manca nell’insieme. Richiede un tempo O(n), ma usa O(n) di memoria aggiuntiva, che i metodi della somma e dello XOR evitano.

Python

def missingNumber(nums):
    # Scrivi il codice qui

Casi di test

Caso 1

Caso 2

Caso 3

Input

nums = [4, 2, 0, 1]

Atteso

Missing Number

Funzione

Vincoli

Esempi

Suggerimenti

Soluzione

Controlla ogni candidato

Sottrai la somma dalla somma prevista

Applica XOR agli indici con i valori

Trappole e casi limite

Domande frequenti4

Problemi simili