Single Number
Hai una lista nums in cui ogni valore compare esattamente due volte, tranne un valore che compare una sola volta. Restituisci il valore che compare una sola volta.
Funzione
- numsinteger-array
- un elenco in cui ogni valore compare due volte, tranne uno
- Restituisceinteger
- il valore che compare una sola volta
Vincoli
1 ≤ nums.length < 104-104 ≤ nums[i] ≤ 104- Ogni valore compare esattamente due volte, tranne un valore che compare esattamente una volta.
Esempi
- Input
- nums = [8, 3, 8]
- Output
- 3
- Spiegazione
- 8 appare due volte e 3 appare una volta, quindi la risposta è 3.
- Input
- nums = [5, -2, 7, 5, 7]
- Output
- -2
- Spiegazione
- 5 e 7 compaiono entrambi due volte, mentre -2 è l’unico valore che compare una sola volta. Una risposta negativa si trova nello stesso modo di una positiva.
- Input
- nums = [42]
- Output
- 42
- Spiegazione
- Una lista con un solo valore non ha affatto coppie, quindi quel valore è la risposta.
+13 test nascosti all’invio
Per approfondire
E se ogni valore comparisse tre volte, tranne uno? XOR da solo non annulla più i gruppi di tre. Riesci comunque a trovare il singolo valore in O(n) tempo e con O(1) memoria aggiuntiva?
Suggerimenti
Aprili uno alla volta. Ognuno rivela un po’ di più.
Se ogni coppia di valori uguali potesse scomparire, rimarrebbe solo la risposta. Esiste un’operazione che trasforma due numeri uguali in niente?
XOR fa:
x ^ xè0ex ^ 0èx. È anche indipendente dall’ordine, quindi le due copie di un valore non devono trovarsi una accanto all’altra per annullarsi.Mantieni una variabile che parte da
0. Esegui XOR con ogni valore dinums, poi restituiscila. Non servono né mappe né ordinamento.
Soluzione
Trovare l’unico valore senza una coppia è un problema di conteggio, e una mappa hash conta ogni valore in un solo passaggio. Il problema è la memoria: una mappa cresce insieme alla lista. XOR elimina del tutto la necessità di contare, perché fare XOR di un valore con sé stesso dà 0. Fai XOR di tutti i valori della lista e ogni coppia si annulla, lasciando il singolo valore in un solo passaggio con una sola variabile.
Conta ogni valore scorrendo
Corretto, ma non termina sui test più grandi
Intuizione
Prendi ciascun valore a turno e scorri l’intera lista per contare quante volte compare. Un valore di una coppia conta 2. Il valore singolo conta 1, quindi restituisci il primo valore il cui conteggio è 1.
È corretto perché i conteggi derivano direttamente dalla definizione della risposta e non richiede memoria aggiuntiva oltre a un contatore.
È lento perché ciascuno degli n valori comporta una scansione completa di n valori. Quando il valore singolo si trova alla fine di una lista di 9.999 elementi, si arriva a quasi 10^8 confronti.
Algoritmo
- Itera su ogni valore in
nums. - Esamina l’intero elenco e conta i valori uguali a esso.
- Se il conteggio è 1, restituisci quel valore.
def singleNumber(nums):
for value in nums:
# count() scans the whole list: O(n) per value.
if nums.count(value) == 1:
return value
return 0Conta con una mappa hash
Intuizione
Ripassare la lista per ogni valore ripete il lavoro. Conta invece tutti i valori in un unico passaggio: una mappa hash da valore a conteggio, in cui ogni passaggio aggiunge 1 al conteggio del valore corrente.
Per [5, -2, 7, 5, 7] la mappa termina con 5 → 2, -2 → 1, 7 → 2. Un secondo passaggio sulla mappa trova la voce con conteggio 1, che è -2.
Ogni valore richiede un aggiornamento della mappa, quindi il tempo è O(n). La mappa contiene circa n/2 voci, ovvero O(n) di memoria aggiuntiva. In C, che non ha una mappa integrata, un array di contatori indicizzato da value + 10^4 svolge lo stesso ruolo perché i valori sono piccoli.
Algoritmo
- Crea una mappa vuota da valore a conteggio.
- Per ogni valore in
nums, aggiungi 1 al suo conteggio. - Esamina la mappa e restituisci il valore il cui conteggio è 1.
def singleNumber(nums):
counts = {}
for value in nums:
counts[value] = counts.get(value, 0) + 1
for value, count in counts.items():
if count == 1:
return value
return 0Applica XOR a tutti i valori
Intuizione
XOR confronta due numeri bit per bit e imposta un bit nei punti in cui sono diversi. Ne conseguono tre fatti: x ^ x = 0, x ^ 0 = x e l’ordine delle operazioni non è importante.
Quindi applica XOR a tutta la lista usando una variabile che parte da 0. Puoi raggruppare nuovamente le operazioni in modo che ogni coppia incontri il suo gemello, e ogni coppia diventa 0. Ciò che resta è 0 ^ single, che corrisponde al valore singolo. Per [8, 3, 8]: 0 ^ 8 = 8, poi 8 ^ 3 = 11, poi 11 ^ 8 = 3.
Funziona anche con i numeri negativi. XOR agisce sui bit della rappresentazione in complemento a due, e due numeri negativi uguali hanno gli stessi bit, quindi si annullano come qualsiasi altra coppia. Il ciclo legge ogni valore una volta e mantiene una sola variabile: tempo O(n) e memoria aggiuntiva O(1).
Algoritmo
- Imposta
resulta 0. - Per ogni valore in
nums, impostaresultaresult ^ value. - Restituisci
result.
def singleNumber(nums):
result = 0
for value in nums:
result ^= value
return result
Trappole e casi limite
Il ciclo XOR è breve, quindi gli errori si nascondono nel punto da cui si inizia e nelle alternative a cui si ricorre.
- Iniziare
resultdanums[0]e poi scorrere tutti i valori, incluso l'indice 0. Il primo valore viene sottoposto a XOR due volte e si annulla da solo. Inizia da 0 oppure salta l'indice 0. - Ordinare e confrontare gli elementi vicini a coppie, poi dimenticare che il singolo valore può essere l'ultimo elemento. In
[1, 1, 2]non esiste alcuna coppia diversa e la risposta è il 2 rimanente. - Usare
2 × sum(distinct values) - sum(nums). Restituisce il numero giusto, ma l'insieme dei valori distinti richiedeO(n)di memoria, che la versione XOR evita. - Aspettarsi che XOR funzioni con altre quantità di occorrenze. Annulla i valori che compaiono un numero pari di volte. Se un valore comparisse tre volte, ne rimarrebbe una copia e la risposta sarebbe errata.
Domande frequenti4
Qual è la complessità temporale di Single Number?
La soluzione XOR richiede un tempo O(n) e uno spazio aggiuntivo O(1), perché legge ogni valore una volta e mantiene una variabile. Anche una mappa hash richiede un tempo O(n), ma necessita di memoria O(n). Contare ogni valore con una nuova scansione richiede O(n²).
Perché XOR risolve il problema del numero singolo?
Eseguire XOR tra un numero e se stesso dà 0, eseguire XOR con 0 non cambia nulla e l’ordine delle operazioni non ha importanza. Quindi, quando esegui XOR sull’intera lista, ogni coppia può essere raggruppata e si annulla a 0. Rimane solo il valore senza una coppia.
Il trucco XOR funziona con i numeri negativi?
Sì. XOR opera sui bit che memorizzano il numero, e i numeri negativi sono memorizzati in complemento a due. Due numeri negativi uguali hanno bit identici, quindi si annullano proprio come quelli positivi. In [5, -2, 7, 5, 7] il risultato è -2.
Come si risolve quando gli altri valori compaiono tre volte?
XOR annulla le coppie, non le triplette, quindi in questo caso non funziona. Invece, conta quanti valori hanno impostato ciascuno dei 32 bit. Per ogni bit, il conteggio modulo 3 corrisponde al bit del singolo valore, perché le triplette aggiungono multipli di 3. Questo richiede comunque un tempo O(n) e memoria aggiuntiva O(1).
Problemi simili
Problemi che usano le stesse idee. Risolverne due o tre è ciò che fissa uno schema.
Python
def singleNumber(nums):
# Scrivi il codice quiCaso 1
Caso 2
Caso 3
Input
nums = [8, 3, 8]
Atteso
3