Contains Duplicate
Ti viene fornito un array di numeri interi nums. Restituisci true se un valore compare almeno due volte e false se tutti i valori sono diversi.
Funzione
- numsinteger-array
- gli interi da controllare
- Restituisceboolean
- true se un valore compare almeno due volte, false altrimenti
Vincoli
1 ≤ nums.length ≤ 104-109 ≤ nums[i] ≤ 109
Esempi
- Input
- nums = [3, 1, 4, 1, 5]
- Output
- true
- Spiegazione
- Il valore
1compare all'indice 1 e di nuovo all'indice 3, quindi la risposta ètrue.
- Input
- nums = [2, 7, 1, 8]
- Output
- false
- Spiegazione
2,7,1e8sono quattro valori diversi, quindi niente si ripete.
- Input
- nums = [-4, 4, 0]
- Output
- false
- Spiegazione
-4e4hanno lo stesso valore assoluto ma sono numeri diversi, e0compare una volta, quindi la risposta èfalse.
+17 test nascosti all’invio
Per approfondire
Puoi fermarti appena trovi il primo valore ripetuto, invece di leggere sempre l’intero array?
Suggerimenti
Aprili uno alla volta. Ognuno rivela un po’ di più.
Confrontare ogni valore con tutti gli altri funziona, ma per
10^4valori significa circa5 × 10^7confronti. Che cosa potresti ricordare dei valori che hai già esaminato?Una ripetizione significa che il valore corrente è uno che hai già incontrato. Un insieme hash risponde alla domanda «ho già incontrato questo valore?» in tempo costante in media.
Scorri l’array una volta con un insieme vuoto. Per ogni valore, restituisci
truese è già nell’insieme; altrimenti aggiungilo. Se il ciclo termina, tutti i valori erano diversi.
Soluzione
Un duplicato è un valore che hai già incontrato, e il lavoro consiste nel rispondere rapidamente a «l’ho già incontrato?». Confrontare ogni coppia risponde alla domanda, ma per n = 10^4 significa fare n(n-1)/2, circa 5 × 10^7 confronti. Ordinando i valori uguali finiscono uno accanto all’altro, mentre un insieme hash risponde alla domanda in O(1) in media, consentendo un’unica scansione.
Ordina, poi confronta gli elementi adiacenti
Intuizione
In un array ordinato, i valori uguali si trovano uno accanto all'altro. [3, 1, 4, 1, 5] viene ordinato come [1, 1, 3, 4, 5], e i due 1 ora sono adiacenti. Quindi, dopo l'ordinamento, confronti ogni valore solo con quello immediatamente precedente: n-1 confronti invece dei n(n-1)/2 necessari per provare ogni coppia.
Se nessuna coppia di elementi adiacenti è uguale, allora non ci sono due valori uguali in tutto l'array: qualsiasi valore compreso tra due copie di x nell'ordine ordinato dovrebbe essere sia maggiore o uguale a x sia minore o uguale a x, quindi sarebbe un'altra copia di x.
L'ordinamento determina la complessità, pari a O(n log n). Ordinare nums sul posto non richiede un array aggiuntivo, ma riordina l'input del chiamante; se ciò non è consentito, ordina una copia, che richiede O(n) spazio.
Algoritmo
- Ordina
numsin ordine crescente. - Fai scorrere
ida 1 all'ultimo indice. - Se
nums[i]è uguale anums[i-1], restituiscitrue. - Dopo il ciclo, restituisci
false.
def containsDuplicate(nums):
nums.sort()
# After sorting, equal values sit next to each other.
for i in range(1, len(nums)):
if nums[i] == nums[i - 1]:
return True
return FalseUn passaggio con un insieme hash
Intuizione
Scorri l’array una volta e conserva ogni valore che hai già incontrato in un insieme hash. Prima di aggiungere un valore, chiedi all’insieme se è già presente. Per [3, 1, 4, 1, 5] l’insieme cresce fino a {3, 1, 4} e, quando arriva il secondo 1, l’insieme lo contiene già, quindi restituisci true senza leggere il 5.
L’insieme contiene sempre esattamente i valori che precedono la posizione corrente, quindi una corrispondenza significa che il valore corrente è apparso prima, mentre arrivare alla fine senza trovarne una significa che tutti i valori sono diversi.
La ricerca e l’inserimento in un insieme hash richiedono in media O(1) tempo, quindi l’intera scansione è O(n). Il prezzo da pagare è la memoria: se non ci sono ripetizioni, l’insieme finirà per contenere tutti gli n valori.
Algoritmo
- Crea un insieme hash vuoto
seen. - Per ogni valore in
nums, se è inseen, restituiscitrue. - Altrimenti, aggiungilo a
seen. - Dopo il ciclo, restituisci
false.
def containsDuplicate(nums):
seen = set()
for num in nums:
if num in seen:
return True
seen.add(num)
return False
Trappole e casi limite
La logica è breve, quindi i bug riguardano i limiti dei cicli e ciò che confronti.
- Confrontare ogni coppia facendo partire il ciclo interno da
j = i. Ogni valore corrisponde quindi a se stesso e il risultato è sempretrue. - Confrontare gli elementi vicini senza ordinare prima. In
[9, 1, 2, 3, 9]i due9non sono uno accanto all'altro. - Far partire il ciclo sugli elementi vicini dall'indice 0 e leggere
nums[-1]. Parti da 1: un array con un solo valore restituisce correttamentefalse. - Considerare uguali i valori con lo stesso valore assoluto, per esempio calcolando l'hash di
abs(x).-4e4sono numeri diversi. - Scrivere un comparatore di ordinamento in C che restituisce
x - y. In questo caso la differenza rimane entro±2 × 10^9, al di sotto del limite diint,2^31-1 = 2147483647, quindi rientra nei limiti; con valori vicini ai limiti diint, si verifica un overflow e l'ordinamento risulta errato. Restituisci invece(x > y) - (x < y).
Domande frequenti4
Qual è la complessità temporale di Contains Duplicate?
La soluzione con insieme hash richiede in media O(n) di tempo e usa O(n) di spazio aggiuntivo. Ordinare prima richiede O(n log n) di tempo e nessun array aggiuntivo se puoi riordinare l’input. Confrontare ogni coppia richiede O(n²) di tempo.
Riesci a risolvere Contains Duplicate senza spazio extra?
Sì, se puoi riordinare l'array: ordinalo sul posto e confronta ogni valore con il suo vicino. In questo modo, la struttura dati O(n) viene sostituita da un tempo di O(n log n). Senza riordinare e senza memoria aggiuntiva, l'unica opzione rimasta è il controllo delle coppie in O(n²).
Perché un insieme hash rende veloce il controllo?
Un insieme hash memorizza i valori in base al loro hash, quindi verificare se contiene un valore richiede in media un tempo costante invece di una scansione. Ogni elemento richiede una ricerca e un inserimento, il che rende lineare l’intero passaggio.
Confrontare la dimensione dell'insieme con la lunghezza dell'array è una soluzione valida?
Sì. Creare un insieme a partire da tutti gli elementi di nums e verificare se è più piccolo dell’array dà la risposta corretta in tempo O(n). La versione con il ciclo è spesso migliore perché restituisce il risultato non appena incontra la prima ripetizione, mentre creare l’intero insieme legge sempre tutti i valori.
Problemi simili
Problemi che usano le stesse idee. Risolverne due o tre è ciò che fissa uno schema.
Python
def containsDuplicate(nums):
# Scrivi il codice quiCaso 1
Caso 2
Caso 3
Input
nums = [3, 1, 4, 1, 5]
Atteso
true