Intersection of Two Arrays
Ti vengono forniti due array di interi, nums1 e nums2. Restituisci tutti i valori presenti in entrambi gli array, ordinati in ordine crescente. Ogni valore condiviso compare una sola volta nella risposta, indipendentemente da quante volte si ripete in ciascun array.
Funzione
- nums1integer-array
- il primo elenco di numeri interi
- nums2integer-array
- la seconda lista di numeri interi
- Restituisceinteger-array
- i valori presenti in entrambe le liste, una sola volta ciascuno, in ordine crescente
Vincoli
1 ≤ nums1.length, nums2.length ≤ 5000-105 ≤ nums1[i], nums2[i] ≤ 105- Almeno un valore compare in entrambi gli array.
Esempi
- Input
- nums1 = [6, 2, 9, 2, 4]nums2 = [4, 4, 1, 6]
- Output
- [4, 6]
- Spiegazione
4e6sono presenti in entrambi gli array.4compare due volte innums2ma è elencato una sola volta, mentre2e9non compaiono mai innums2.
- Input
- nums1 = [-3, 0, 7]nums2 = [7, -3, -3, 5]
- Output
- [-3, 7]
- Spiegazione
-3e7sono presenti in entrambi gli array. In ordine crescente, viene prima-3, anche se innums2viene prima7.
+16 test nascosti all’invio
Per approfondire
Che cosa succede se nums1 contiene 10 valori e nums2 ne contiene un milione, già ordinati? Quale approccio sceglieresti e la ricerca binaria può essere più efficiente di una scansione completa?
Suggerimenti
Aprili uno alla volta. Ognuno rivela un po’ di più.
Per ogni valore di
nums1potresti scorrere tuttonums2. Con 5000 valori in ciascun array, si arriva a2.5 × 10^7confronti. Quale domanda stai ponendo ripetutamente?La domanda ripetuta è «questo valore è presente nell'altro array?». Un insieme hash costruito a partire da un array risponde in tempo costante in media.
Crea un insieme a partire da
nums1. Scorrinums2; quando un valore è nell'insieme, aggiungilo alla risposta e rimuovilo dall'insieme, così una sua copia successiva non potrà essere aggiunta di nuovo. Ordina la risposta prima di restituirla.
Soluzione
Due dettagli determinano questo problema: un valore che si ripete in entrambi gli array va inserito una sola volta nella risposta, che deve inoltre essere ordinata. Confrontare ogni coppia funziona, ma richiede n × m confronti, 2.5 × 10^7 quando entrambi gli array contengono 5000 valori. Ordinare entrambi gli array consente a due puntatori di individuare i valori condivisi in ordine, mentre un insieme hash di uno degli array permette di rispondere in tempo costante alla domanda «questo valore è presente in nums1?».
Confronta ogni coppia
Corretto, ma non termina sui test più grandi
Intuizione
Esamina ogni valore di nums1 e scandisci nums2 alla sua ricerca. Interrompi la scansione al primo riscontro e salta un valore già presente nella risposta, così [8, 8, 8, 8] confrontato con [8, 8] restituisce un solo 8, non quattro. Ordina la risposta alla fine.
È corretto perché un valore viene inserito nella risposta esattamente quando una sua occorrenza in nums1 trova un riscontro in nums2, e il salto impedisce di inserirlo due volte.
È lento perché ogni valore di nums1 può scandire tutto nums2. Con 5000 valori in ciascun array, si arriva fino a 2.5 × 10^7 confronti e, nei test più grandi, la maggior parte dei valori non trova riscontri, quindi la maggior parte delle scansioni arriva fino alla fine.
Algoritmo
- Inizia con un elenco di risposte vuoto.
- Per ogni valore
ainnums1, saltalo se è già nella risposta. - Altrimenti, scorri
nums2; al primo valore uguale aa, aggiungiaalla risposta e interrompi la scansione. - Ordina la risposta in ordine crescente e restituiscila.
def intersection(nums1, nums2):
result = []
for a in nums1:
if a in result:
continue
# Look for a anywhere in nums2.
for b in nums2:
if a == b:
result.append(a)
break
result.sort()
return resultOrdina entrambi, poi scorri con due puntatori
Intuizione
Una volta ordinato, l'esempio 1 diventa [2, 2, 4, 6, 9] e [1, 4, 4, 6]. Posiziona il puntatore i all'inizio del primo array e j all'inizio del secondo. Il puntatore sul valore più piccolo avanza: quel valore non può corrispondere a nessun valore più avanti nell'altro array, dove tutti i valori sono almeno altrettanto grandi. Quando entrambi i puntatori indicano lo stesso valore, questo è comune, quindi aggiungilo e sposta entrambi i puntatori.
Nell'esempio: 2 > 1 sposta j, entrambi i 2 sono più piccoli di 4 e spostano i, 4 = 4 aggiunge 4, il secondo 4 è più piccolo di 6 e sposta j, e 6 = 6 aggiunge 6. Un valore presente più volte su entrambi i lati, come 2 in [2, 2, 3] e [2, 2], corrisponde più di una volta; confrontarlo con l'ultimo valore aggiunto mantiene una sola copia. Il risultato è già ordinato, senza bisogno di passaggi aggiuntivi.
L'ordinamento ha un costo di O(n log n + m log m), mentre la scansione è O(n + m) perché ogni passaggio sposta almeno un puntatore. La maggior parte delle versioni ordina delle copie, con un costo in memoria di O(n + m). Se puoi riordinare gli input, ordinali sul posto, come fa il codice C, e l'unica memoria aggiuntiva è quella del risultato.
Algoritmo
- Ordina entrambi gli array.
- Imposta
i = 0ej = 0. - Mentre entrambi i puntatori sono all'interno dei rispettivi array, sposta il puntatore sul valore più piccolo.
- In caso di valori uguali, aggiungi il valore a meno che non sia uguale all'ultimo valore aggiunto, poi sposta entrambi i puntatori.
- Restituisci la risposta.
def intersection(nums1, nums2):
a = sorted(nums1)
b = sorted(nums2)
i, j = 0, 0
result = []
while i < len(a) and j < len(b):
if a[i] < b[j]:
i += 1
elif a[i] > b[j]:
j += 1
else:
# A shared value: keep it once, even if it repeats.
if not result or result[-1] != a[i]:
result.append(a[i])
i += 1
j += 1
return resultInsieme hash del primo array
Intuizione
Inserisci ogni valore di nums1 in un insieme hash. Nell'esempio 1 l'insieme è {6, 2, 9, 4}: il 2 ripetuto viene eliminato al momento dell'inserimento. Poi scorri nums2 e chiedi all'insieme se contiene ciascun valore, in tempo costante. Il primo 4 è presente, quindi viene aggiunto alla risposta. Il secondo 4 non deve esserci, quindi rimuovi un valore dall'insieme non appena corrisponde. 1 non è presente, mentre 6 sì, e si ottiene [4, 6].
La rimozione in caso di corrispondenza fa sì che ogni valore compaia una sola volta: dopo la prima corrispondenza, il valore viene rimosso dall'insieme, quindi le copie successive in nums2 non trovano nulla. Ogni valore aggiunto è presente in entrambi gli array e ogni valore condiviso viene aggiunto quando arriva la sua prima copia in nums2.
La creazione dell'insieme e lo scorrimento richiedono in media O(n + m). La risposta viene generata nell'ordine di nums2, quindi ordinala alla fine; contiene k ≤ min(n, m) valori, per cui il costo è O(k log k). C non ha un insieme integrato, quindi il codice C usa un array di flag indicizzato da value + 10^5, che funziona perché i valori sono limitati.
Algoritmo
- Crea un insieme hash
firsta partire danums1. - Per ogni valore in
nums2, se è infirst, aggiungilo alla risposta e rimuovilo dafirst. - Ordina la risposta in ordine crescente.
- Restituiscila.
def intersection(nums1, nums2):
first = set(nums1)
result = []
for num in nums2:
if num in first:
result.append(num)
# Remove it so a repeat in nums2 is not added twice.
first.remove(num)
result.sort()
return result
Trappole e casi limite
La maggior parte delle risposte sbagliate in questo caso è dovuta ai valori ripetuti e all’ordine dell’output.
- Aggiungere un valore ogni volta che corrisponde.
[2, 2, 3, 3, 3]e[3, 2, 2]hanno due valori in comune, quindi la risposta è[2, 3], non[3, 2, 2]. - Restituire i valori nell’ordine in cui li hai trovati. La scansione dell’hash set segue
nums2, quindi[7, -3]deve comunque essere ordinato come[-3, 7]. - Ordinare i numeri come testo. In JavaScript,
sort()senza un comparatore confronta le stringhe, quindi[100000, 99]resta in quest’ordine. Passa(x, y) => x - y. - Usare l’intersezione di insiemi e dimenticare l’ordine. In Python,
set(nums1) & set(nums2)trova i valori corretti in un ordine non specificato; racchiudila insorted. - Indicizzare un array di flag usando il valore grezzo.
-3non è un indice valido; sposta prima ogni valore di10^5.
Domande frequenti4
Qual è la complessità temporale dell’intersezione di due array?
Con un insieme hash, trovare i valori condivisi richiede in media O(n + m) e ordinare i k valori della risposta aggiunge O(k log k); l’insieme usa O(n) spazio. Ordinare entrambi gli array e scorrerli con due puntatori richiede O(n log n + m log m). Confrontare ogni coppia richiede O(n × m).
Dovresti usare un insieme hash o due puntatori?
Usa l'insieme hash quando gli array non sono ordinati e hai memoria disponibile: richiede il minor lavoro. Usa due puntatori quando entrambi gli array sono già ordinati, oppure quando la memoria è limitata e puoi ordinarli sul posto. La scansione non richiede un insieme e produce la risposta in ordine.
Come mantieni i valori ripetuti nell’intersezione?
Se un valore deve comparire tante volte quante compare in entrambi gli array, così che [3, 1, 3, 3] e [3, 3] restituiscano [3, 3], sostituisci il set con una mappa dei conteggi. Conta i valori di nums1 e, per ogni valore di nums2 il cui conteggio è maggiore di zero, aggiungilo e riduci il suo conteggio. Nel ciclo a due puntatori, elimina il controllo rispetto all’ultimo valore aggiunto.
Come trovi l’intersezione quando un array è troppo grande per la memoria?
Costruisci l'insieme hash a partire dall'array che ci sta e leggi quello più grande a blocchi, verificando ogni valore rispetto all'insieme e rimuovendolo in caso di corrispondenza. La memoria rimane pari alle dimensioni dell'array più piccolo. Se nessuno dei due array ci sta, ordina entrambi su disco ed esegui la scansione a due puntatori sui file ordinati.
Problemi simili
Problemi che usano le stesse idee. Risolverne due o tre è ciò che fissa uno schema.
Python
def intersection(nums1, nums2):
# Scrivi il codice quiCaso 1
Caso 2
Input
nums1 = [6, 2, 9, 2, 4] nums2 = [4, 4, 1, 6]
Atteso
[4, 6]