Median of Two Sorted Arrays
Ti vengono fornite due liste di interi, nums1 e nums2, ciascuna ordinata dal valore più piccolo al più grande e contenente almeno un valore. Restituisci la mediana di tutti i loro valori insieme, come testo.
Se il numero totale di valori è dispari, la mediana è il valore centrale, ad esempio "4". Se è pari, è la media dei due valori centrali, ad esempio "2.5" o "-0.5". Scrivi un numero intero senza virgola decimale e lo zero come "0", mai "-0". Punta a un tempo di esecuzione di O(log(min(m, n))).
Funzione
- nums1integer-array
- il primo elenco, ordinato dal più piccolo al più grande
- nums2integer-array
- la seconda lista, ordinata dal più piccolo al più grande
- Restituiscestring
- la mediana di tutti i valori, come testo quale "4" o "-2.5"
Vincoli
1 ≤ nums1.length, nums2.length ≤ 3000-106 ≤ nums1[i], nums2[i] ≤ 106- Entrambi gli elenchi sono ordinati in ordine non decrescente e i valori possono ripetersi.
Esempi
- Input
- nums1 = [1, 4]nums2 = [2, 7, 9]
- Output
- "4"
- Spiegazione
- Insieme, i valori sono 1, 2, 4, 7, 9. Cinque valori hanno un valore centrale, il terzo, che è 4.
- Input
- nums1 = [1, 2]nums2 = [3, 4]
- Output
- "2.5"
- Spiegazione
- Nel complesso i valori sono 1, 2, 3, 4. I due valori centrali sono 2 e 3, la loro somma è 5 e la metà di 5 è 2.5.
- Input
- nums1 = [-7, -3]nums2 = [-2, 0]
- Output
- "-2.5"
- Spiegazione
- Insieme i valori sono -7, -3, -2, 0. I valori centrali -3 e -2 sommano -5, e la metà di -5 è -2.5.
Per approfondire
Riesci a usare lo stesso taglio per trovare il k-esimo valore più piccolo delle due liste, per qualsiasi k, in tempo logaritmico?
Suggerimenti
Aprili uno alla volta. Ognuno rivela un po’ di più.
Unendo le due liste si trova la mediana in
O(m + n). Per fare di meglio, pensa alla mediana come a un taglio: una linea che divide tutti im + nvalori in una metà inferiore e una metà superiore della stessa dimensione.La metà inferiore è un prefisso di
nums1più un prefisso dinums2. Se prendeivalori danums1, segue il conteggio danums2. Il taglio è corretto quando l’ultimo valore preso da ciascuna lista non è maggiore del primo valore rimasto nell’altra.Ricerca binaria su
inell’elenco più corto. Se l’ultimo valore preso danums1è troppo grande, prendine meno; se l’ultimo valore preso danums2è troppo grande, prendine di più. Nel punto di taglio corretto, la mediana si ottiene dal valore più grande sotto il taglio e da quello più piccolo sopra. Somma questi due interi e dimezza tu la somma.
Soluzione
Unire gli elenchi dà la mediana in O(m + n), ma la maggior parte dei valori letti non può cambiare la risposta. La mediana dipende solo da dove cade il taglio tra la metà inferiore e quella superiore, e un numero determina quel taglio: quanti valori la metà inferiore prende dall'elenco più corto. La ricerca binaria lo trova in O(log(min(m, n))) passaggi.
Unisci i due elenchi
Intuizione
Unisci gli elenchi come fa merge sort, in un unico elenco ordinato merged. Con total = m + n, somma merged[(total-1)/2] e merged[total/2], usando la divisione intera. Se il totale è dispari, entrambi sono il valore centrale; se è pari, sono i due valori centrali, quindi in entrambi i casi la metà della somma è la mediana.
Anche se ti fermi al valore centrale, i passaggi di unione attraversano più della metà dei valori, quindi il tempo è O(m + n).
Algoritmo
- Unisci le liste in
merged, scegliendo sempre il valore corrente più piccolo, poi aggiungi il resto della lista rimasta. - Con
total = m + n, sommamerged[(total-1)/2]emerged[total/2]. - Restituisci metà della somma come testo: dividi per 2 una somma pari; per una somma dispari scrivi il segno, la metà del valore assoluto e
.5.
def half_text(total):
# total / 2 as text, from integers only: 5 -> "2.5", -1 -> "-0.5", 6 -> "3"
if total % 2 == 0:
return str(total // 2)
sign = "-" if total < 0 else ""
return sign + str(abs(total) // 2) + ".5"
def findMedianSortedArrays(nums1, nums2):
# Merge the two sorted lists into one, the way merge sort does.
merged = []
i = j = 0
while i < len(nums1) and j < len(nums2):
if nums1[i] <= nums2[j]:
merged.append(nums1[i])
i += 1
else:
merged.append(nums2[j])
j += 1
merged.extend(nums1[i:])
merged.extend(nums2[j:])
total = len(merged)
# For an odd total both indexes point at the one middle value.
return half_text(merged[(total - 1) // 2] + merged[total // 2])Ricerca binaria sul taglio
Intuizione
Fai in modo che la metà inferiore contenga half = (m+n+1)/2 valori: quello in più quando il totale è dispari. Prende i valori dall’inizio di nums1 e j = half-i dall’inizio di nums2. Il taglio è corretto quando nessun elemento al di sotto è maggiore di un elemento al di sopra. Ogni lista è ordinata, quindi restano due verifiche: left1 ≤ right2 e left2 ≤ right1, dove left è l’ultimo valore che una lista assegna alla metà inferiore e right il primo che mantiene. Un lato mancante equivale a meno o più infinito.
Se left1 > right2, i è troppo grande; se left2 > right1, è troppo piccolo. Quindi i viene cercato con una ricerca binaria da 0 a m. Su [1, 2] e [3, 4], i = 1 non va bene perché left2 = 3 > right1 = 2, mentre i = 2 va bene: (2 + 3) / 2 = 2.5.
Algoritmo
- Fai in modo che
nums1sia la lista più corta; ponihalf = (m+n+1)/2. - Esegui una ricerca binaria di
idalo = 0ahi = m, conj = half-i. - Leggi
left1 = nums1[i-1],right1 = nums1[i],left2 = nums2[j-1]eright2 = nums2[j], considerando infinito oltre un’estremità. - Se
left1 > right2, impostahi = i-1. Seleft2 > right1, impostalo = i+1. - Altrimenti, se il totale è dispari, restituisci
max(left1, left2). Se il totale è pari, dimezzamax(left1, left2) + min(right1, right2)come testo.
def half_text(total):
# total / 2 as text, from integers only: 5 -> "2.5", -1 -> "-0.5", 6 -> "3"
if total % 2 == 0:
return str(total // 2)
sign = "-" if total < 0 else ""
return sign + str(abs(total) // 2) + ".5"
def findMedianSortedArrays(nums1, nums2):
# Binary search over the shorter list.
if len(nums1) > len(nums2):
nums1, nums2 = nums2, nums1
m, n = len(nums1), len(nums2)
half = (m + n + 1) // 2 # size of the left half; it gets the extra value when m + n is odd
lo, hi = 0, m
while lo <= hi:
i = (lo + hi) // 2 # values the left half takes from nums1
j = half - i # values it takes from nums2
# An empty side counts as minus or plus infinity.
left1 = nums1[i - 1] if i > 0 else float("-inf")
right1 = nums1[i] if i < m else float("inf")
left2 = nums2[j - 1] if j > 0 else float("-inf")
right2 = nums2[j] if j < n else float("inf")
if left1 > right2:
hi = i - 1 # too many values from nums1
elif left2 > right1:
lo = i + 1 # too few values from nums1
else:
left_max = max(left1, left2)
if (m + n) % 2 == 1:
return str(left_max)
return half_text(left_max + min(right1, right2))
return "" # not reached: sorted input always has a valid split
Trappole e casi limite
- Dimezzare usando i numeri in virgola mobile. Python stampa una mediana intera come
3.0, mentre%fdi C stampa 2.5 come2.500000. Mantieni la somma come intero. - Scrivere il quoziente intero e
.5per una somma dispari negativa.-1 / 2vale 0 in C e Java, dando 0.5 per -0.5;-5 // 2vale -3 in Python, dando -3.5 per -2.5. Dimezza il valore assoluto e rimetti il segno. - Scrivere
-0. I valori centrali -1 e 1 hanno somma 0 e la risposta è"0". Prendi il segno dalla somma. - Cercare nella lista più lunga.
j = half-ipuò essere minore di 0 o superaren. Scambia prima le liste. - Leggere
nums1[i-1]quandoi = 0, come con[9]e[1, 2]. Usa gli infiniti per i valori mancanti.
Domande frequenti3
Qual è la complessità temporale di Median of Two Sorted Arrays?
La ricerca binaria sul taglio richiede O(log(min(m, n))) di tempo e O(1) di spazio, perché ogni passaggio dimezza i possibili tagli nella lista più corta. La fusione richiede O(m + n): per due liste di 3000 elementi, circa 12 passaggi contro 6000.
Perché eseguire una ricerca binaria sull’array più corto?
Poiché j = half-i. Con i che scorre la lista più corta, j rimane tra 0 e la lunghezza della lista più lunga, quindi ogni lettura è nell'intervallo o oltre una fine che consideri come infinito.
Come si restituisce la mediana senza virgola mobile?
Somma i due valori centrali come interi. Dividi una somma pari per 2. Per una somma dispari, scrivi la metà del suo valore assoluto e .5, con un segno meno quando la somma è negativa: -1 diventa "-0.5".
Problemi simili
Problemi che usano le stesse idee. Risolverne due o tre è ciò che fissa uno schema.
def findMedianSortedArrays(nums1, nums2):
# Scrivi il codice quiTest #1
Test #2
Test #3
Argomenti
nums1 = [1, 4] nums2 = [2, 7, 9]
Output atteso
"4"