Find the Duplicate Number
Ricevi un array nums di n+1 interi, ciascuno compreso tra 1 e n. Esattamente un valore compare più di una volta, anche molte volte, e devi restituire quel valore.
Risolvi il problema senza modificare nums e usando solo una quantità costante di memoria aggiuntiva.
Funzione
- numsinteger-array
- n+1 interi, ciascuno compreso tra 1 e n
- Restituisceinteger
- il valore che compare più di una volta
Vincoli
1 ≤ n ≤ 104nums.length == n+11 ≤ nums[i] ≤ n- Esattamente un valore compare due o più volte; ogni altro valore compare al massimo una volta.
Esempi
- Input
- nums = [2, 5, 1, 3, 5, 4]
- Output
- 5
- Spiegazione
- Qui
nè 5, e 5 si trova nelle posizioni 1 e 4, quindi la risposta è 5. Ogni altro valore da 1 a 5 compare una volta.
- Input
- nums = [4, 2, 4, 1, 4]
- Output
- 4
- Spiegazione
- 4 compare tre volte, nelle posizioni 0, 2 e 4, mentre 3 non compare affatto. Una ripetizione può sostituire diversi valori mancanti, quindi la risposta è 4.
+17 test nascosti all’invio
Per approfondire
La ricerca binaria sui valori mantiene entrambe le regole in O(n log n) di tempo. Riesci a mantenerle in O(n) di tempo?
Suggerimenti
Aprili uno alla volta. Ognuno rivela un po’ di più.
Ogni valore è compreso tra 1 e
n, e l'array ha posizioni da 0 an. Quindi ogni valore è anche una posizione valida. Parti dalla posizione 0, passa alla posizionenums[0], poi alla posizione indicata da quel valore, e così via. Che cosa deve succedere a questo percorso?La camminata non si ferma mai e ha solo
n+1posizioni da visitare, quindi entra in un ciclo. La posizione in cui entra nel ciclo viene raggiunta da due posizioni diverse, ed entrambe hanno quella posizione come valore.Trova l'ingresso del ciclo con due puntatori dalla posizione 0: uno avanza di un salto per turno, l'altro di due, finché non si trovano nella stessa posizione. Poi riporta uno a 0 e spostali entrambi di un salto alla volta. Si incontrano all'ingresso, che è la risposta.
Soluzione
Un insieme hash o un ordinamento trova subito il valore ripetuto, ma entrambi infrangono le regole: l'insieme richiede memoria per ogni valore e l'ordinamento modifica nums. La soluzione sta nei numeri. Ogni valore è compreso tra 1 e n, quindi è anche una posizione valida nell'array. Leggi ogni valore come un collegamento a un'altra posizione e, seguendo i collegamenti a partire dalla posizione 0, finirai sempre in un ciclo il cui ingresso è il duplicato. I puntatori veloce e lento di Floyd trovano quell'ingresso usando due interi.
Confronta ogni coppia
Corretto, ma non termina sui test più grandi
Intuizione
Il valore ripetuto si trova almeno in due posizioni i < j. Confronta ogni posizione con tutte quelle successive; la prima coppia con valori uguali fornisce la risposta. Nel primo esempio, la posizione 1 contiene 5 e la scansione dalla posizione 2 in poi trova un altro 5 alla posizione 4.
In questo modo rispetti entrambe le regole: non viene scritto nulla e l’unica memoria utilizzata è costituita da due contatori del ciclo. È lento perché confronta le coppie. Con n+1 = 10,001 valori e entrambe le copie vicine alla fine, controlla circa 5 × 10^7 coppie.
Algoritmo
- Per ogni posizione
ida 0 fino alla fine: - Per ogni posizione
jsuccessiva ai, confrontanums[i]connums[j]. - Restituisci
nums[i]alla prima corrispondenza.
def findDuplicate(nums):
n = len(nums)
for i in range(n):
for j in range(i + 1, n):
if nums[i] == nums[j]:
return nums[i]
return -1 # unreachable: the input always holds a repeatRicerca binaria sul valore
Intuizione
Cerca nell'intervallo dei valori, non delle posizioni. Scegli una soglia m e conta quante voci di nums sono al massimo m.
Se il duplicato d è maggiore di m, i valori da 1 a m compaiono ciascuno al massimo una volta, quindi il conteggio è al massimo m. Se d è al massimo m, ogni valore maggiore di m compare al massimo una volta, quindi al massimo n-m voci sono maggiori di m e almeno m+1 sono al massimo m. Quindi il test "count > m" è falso per ogni m minore di d e vero da d in poi. La ricerca binaria trova il primo m per cui diventa vero, che è d.
Nel secondo esempio, n è 4. Per m = 2, le voci 2 e 1 danno un conteggio di 2, non superiore a 2, quindi la risposta è maggiore di 2. Per m = 3 il conteggio è ancora 2, quindi la risposta è 4. Ogni iterazione legge l'intero array una volta e dimezza l'intervallo, quindi il lavoro è O(n log n): circa 14 passaggi su 10,001 valori.
Algoritmo
- Imposta
low= 1 ehigh=n, la lunghezza dinumsmeno uno. - Mentre
low < high, prendimida metà tra i due. - Conta gli elementi di
numsche sono al massimomid. - Se il conteggio è maggiore di
mid, impostahigh=mid; altrimenti impostalow=mid+1. - Restituisci
low.
def findDuplicate(nums):
low, high = 1, len(nums) - 1
while low < high:
mid = (low + high) // 2
# How many values fall in 1..mid?
count = 0
for x in nums:
if x <= mid:
count += 1
if count > mid:
high = mid # 1..mid holds more values than it has room for
else:
low = mid + 1 # the repeat is above mid
return lowRilevamento del ciclo di Floyd sui collegamenti dei valori
Intuizione
Leggi l’array come un insieme di collegamenti: la posizione i punta alla posizione nums[i]. Ogni posizione da 0 a n ha esattamente un collegamento in uscita e ogni collegamento arriva in una posizione da 1 a n. Nel primo esempio i collegamenti sono 0 → 2, 1 → 5, 2 → 1, 3 → 3, 4 → 5 e 5 → 4.
Parti dalla posizione 0 e segui i collegamenti. Il percorso non può mai interrompersi, perché ogni posizione ha un collegamento e ci sono solo n+1 posizioni, quindi deve tornare su una posizione già visitata. Da quel momento, gira all’infinito. Il percorso è formato da una coda seguita da un ciclo e ha la forma della lettera ρ. Nel primo esempio il percorso è 0, 2, 1, 5, 4, 5, 4 e così via: la coda è 0, 2, 1 e il ciclo è 5, 4. La posizione 3 punta a sé stessa, ma il percorso non la raggiunge e questo non crea problemi.
L’ingresso del ciclo è il duplicato. Il percorso entra in 5 due volte da posizioni diverse: una volta dalla fine della coda (la posizione 1, perché nums[1] è 5) e una volta dalla fine del ciclo (la posizione 4, perché nums[4] è 5). Due posizioni diverse contengono il valore 5, quindi 5 si ripete. La coda contiene sempre la posizione 0, perché nessun valore è 0 e nessun collegamento punta mai a essa, quindi l’ingresso ha sempre questi due percorsi distinti in entrata. Si ripete esattamente un valore, quindi l’ingresso è quel valore.
Ora trova l’ingresso con due puntatori, come nel rilevamento dei cicli in una lista concatenata. Nella fase 1, slow segue un collegamento a ogni iterazione e fast ne segue due, finché si trovano sulla stessa posizione all’interno del ciclo. Nel primo esempio si incontrano in 4. Nella fase 2, rimetti slow in posizione 0, lascia fast dov’è e spostali entrambi di un collegamento a ogni iterazione. Si incontrano all’ingresso.
Perché la fase 2 funziona: supponi che la coda richieda T collegamenti per raggiungere l’ingresso e che il ciclo abbia C posizioni. Quando i puntatori si sono incontrati, slow aveva fatto s passi e fast 2s. Si trovavano entrambi nello stesso punto, quindi gli s passi in più di fast corrispondevano a un numero intero di giri del ciclo. Dopo altri T passi, slow raggiunge l’ingresso partendo da 0 e fast si trova dove si troverebbe un percorso partito da 0 dopo s+T passi, perché i suoi giri in più non cambiano nulla. Sono T passi per raggiungere l’ingresso più s passi, un numero intero di giri, quindi anche lui si trova all’ingresso. Non possono incontrarsi prima, perché slow è ancora nella coda e fast non esce mai dal ciclo. Nel primo esempio slow passa per 2, 1, 5 mentre fast passa per 5, 4, 5 e si incontrano in 5 dopo T = 3 passi.
Ogni fase richiede O(n) passi, l’unica memoria usata è per due posizioni e nums non viene mai modificato.
Algoritmo
- Tratta ogni posizione
icome un nodo che punta alla posizionenums[i]e fai partire entrambi i puntatori dalla posizione 0. - Fase 1: sposta
slowsunums[slow]efastsunums[nums[fast]]finché non sono uguali. - Fase 2: reimposta
slowa 0. - Spostali entrambi di un collegamento alla volta:
slowsunums[slow]efastsunums[fast], finché non sono uguali. - Restituisci quella posizione: è il valore ripetuto.
def findDuplicate(nums):
# Treat each index i as a node with one link, to nums[i].
# Phase 1: slow moves one link, fast moves two, until they meet in the cycle.
slow = fast = 0
while True:
slow = nums[slow]
fast = nums[nums[fast]]
if slow == fast:
break
# Phase 2: restart one pointer at index 0 and move both one link at a time.
# They meet at the cycle's entrance, the index two positions link to.
slow = 0
while slow != fast:
slow = nums[slow]
fast = nums[fast]
return slow
Trappole e casi limite
La maggior parte delle risposte sbagliate deriva dal confondere le posizioni con i valori o dall'interrompere il metodo di Floyd una fase troppo presto.
- Restituire il punto d'incontro della fase 1. È una posizione qualsiasi del ciclo, non necessariamente il suo ingresso. Nel primo esempio i puntatori si incontrano in 4, ma la risposta è 5.
- Controllare
slow == fastprima della prima mossa. Entrambi partono da 0, quindi il ciclo termina subito. Muoviti prima e poi confronta, oppure falli partire rispettivamente uno e due collegamenti più avanti. - Iniziare la percorrenza da una posizione diversa da 0. Nessun collegamento punta alla posizione 0, poiché nessun valore è 0, e questo garantisce la presenza di una coda. Partire da un'altra posizione può portarti in un ciclo senza accessi dall'esterno, come la posizione 3 nel primo esempio, il cui ingresso non dimostra nulla.
- Supporre che il duplicato compaia esattamente due volte. Il trucco della somma, totale meno
1 + 2 + ... + n, dà 15 meno 10 = 5 nel secondo esempio, ma la risposta è 4. Lo stesso vale per i trucchi basati su XOR. - Eseguire la ricerca binaria sulle posizioni invece che sui valori, oppure verificare
count >= mid. Il numero di valori minori o uguali amè esattamentemse nessun valore da 1 amsi ripete e nessuno manca, quindi solo>distingue i due lati. - Contrassegnare i valori visitati negando
nums[x]o scambiando i valori nelle rispettive posizioni. Entrambi i metodi funzionano, ma modificano l'array, cosa vietata dal compito.
Domande frequenti4
Qual è la complessità temporale di Find the Duplicate Number?
Il rilevamento dei cicli di Floyd richiede O(n) tempo e O(1) memoria aggiuntiva: ciascuna delle sue due fasi segue al massimo un numero di collegamenti pari a pochi multipli di n. La ricerca binaria sui valori richiede O(n log n) tempo e O(1) memoria. Confrontare ogni coppia richiede O(n²).
Perché il rilevamento dei cicli di Floyd trova il numero duplicato?
Se leggi ogni valore come un collegamento dalla sua posizione alla posizione che indica, il percorso dalla posizione 0 deve terminare in un ciclo, perché non si ferma mai e ha solo n+1 posizioni da percorrere. La posizione in cui entra nel ciclo viene raggiunta da due posizioni diverse, una sulla coda e una sul ciclo, quindi due elementi contengono quel valore. Il metodo di Floyd trova l'ingresso di un ciclo con due puntatori, quindi trova il valore ripetuto.
Perché non usare un insieme hash o ordinare l’array?
Entrambi trovano la risposta in tempo O(n) o O(n log n) e, in un programma reale, andrebbe bene qualunque dei due. La consegna li vieta intenzionalmente: un insieme hash usa memoria extra O(n) e l'ordinamento modifica nums oppure richiede una copia completa. Sono proprio le restrizioni a spingerti verso la prospettiva dei cicli.
Perché la formula della somma non funziona per Trovare il numero duplicato?
Sottrarre 1 + 2 + ... + n dalla somma dell’array dà il duplicato solo quando compare esattamente due volte e ogni altro valore compare una volta. Qui la ripetizione può comparire molte volte e sostituire i valori mancanti. In [4, 2, 4, 1, 4] la differenza è 15 meno 10 = 5, che non è nemmeno presente nell’array.
Problemi simili
Problemi che usano le stesse idee. Risolverne due o tre è ciò che fissa uno schema.
Python
def findDuplicate(nums):
# Scrivi il codice quiCaso 1
Caso 2
Input
nums = [2, 5, 1, 3, 5, 4]
Atteso
5