Mediana di due array ordinati
Risolva il problema median-of-two-sorted-arrays in O(log(min(m,n))) usando la ricerca binaria sul confine della partizione dell'array più corto.
Mediana di due array ordinati è una lezione DSA Interview Prep gratuita su CoddyKit. Questa è la lezione 4 di 4. Puoi leggere la lezione completa qui gratuitamente — poi esercitati direttamente nel browser con un editor di codice integrato e un tutor IA disponibile 24/7. Fa parte del percorso di apprendimento DSA Interview Prep, e i tuoi progressi si sincronizzano tra il web e l'app CoddyKit. Il corso DSA Interview Prep include 4 lezioni in totale.
La mediana di due array ordinati
Mediana di due array ordinati (LeetCode 4) è un classico problema difficile. Dati due array ordinati nums1 (di lunghezza m) e nums2 (di lunghezza n), trovi la mediana della sequenza ordinata risultante dalla loro combinazione in tempo O(log(min(m,n))). Un approccio ingenuo unisce entrambi gli array in O(m+n), ma la soluzione ottimale usa la ricerca binaria sui confini delle partizioni. È uno dei problemi difficili più frequenti nei colloqui presso le principali aziende tecnologiche.
# Examples:
nums1 = [1, 3]
nums2 = [2]
# Combined sorted: [1, 2, 3] → median = 2.0
nums1b = [1, 2]
nums2b = [3, 4]
# Combined sorted: [1, 2, 3, 4] → median = (2+3)/2 = 2.5
print('Example 1 median:', 2.0)
print('Example 2 median:', 2.5)
print('Total length:', len(nums1)+len(nums2), 'and', len(nums1b)+len(nums2b))Approccio ingenuo con merge
L'approccio più semplice, O(m+n), consiste nell'unire entrambi gli array ordinati e poi trovare la mediana. L'unione di due array ordinati richiede O(m+n). La mediana di un array di lunghezza L è arr[L//2] se L è dispari, oppure (arr[L//2-1] + arr[L//2]) / 2 se L è pari. Questo approccio è corretto, ma non soddisfa il requisito O(log(min(m,n))). In un colloquio, lo presenti sempre per stabilire un punto di partenza, quindi lo ottimizzi.
def find_median_naive(nums1, nums2):
# Merge two sorted arrays
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 += nums1[i:] + nums2[j:]
L = len(merged)
if L % 2 == 1:
return float(merged[L // 2])
return (merged[L//2 - 1] + merged[L//2]) / 2.0
print(find_median_naive([1,3],[2])) # 2.0
print(find_median_naive([1,2],[3,4])) # 2.5L'idea della partizione
L'intuizione chiave è che la mediana divide l'array combinato in due metà di uguale dimensione. È necessario trovare una partizione di nums1 e una partizione di nums2 tali che: (1) le metà a sinistra abbiano la stessa dimensione totale delle metà a destra; (2) tutti gli elementi nelle metà a sinistra siano ≤ tutti gli elementi nelle metà a destra. Se si cerca con la ricerca binaria il punto di partizione corretto in nums1, la partizione in nums2 viene determinata automaticamente dal vincolo sulla lunghezza totale.
# Partition concept visualised:
# nums1: [1, 3] | [5, 7] (partition after index 1)
# nums2: [2, 4] | [6, 8] (partition after index 1)
# Combined left: [1, 3, 2, 4] = 4 elements
# Combined right: [5, 7, 6, 8] = 4 elements
# Valid if max(left) <= min(right): max(3,4)=4 <= min(5,6)=5 ✓
# Median = (max_left + min_right) / 2 = (4+5)/2 = 4.5
nums1, nums2 = [1,3,5,7], [2,4,6,8]
merged = sorted(nums1+nums2)
print('Merged:', merged)
L = len(merged)
print('Median:', (merged[L//2-1]+merged[L//2])/2 if L%2==0 else merged[L//2])Ricerca binaria sulla partizione
Si esegue la ricerca binaria sull'indice di partizione i di nums1 (l'array più corto). L'indice di partizione j in nums2 è determinato da j = (m+n+1)//2 - i (in modo che le metà a sinistra contengano (m+n+1)//2 elementi). La partizione è valida quando nums1[i-1] ≤ nums2[j] e nums2[j-1] ≤ nums1[i]. La ricerca binaria modifica i aumentandolo o diminuendolo fino a trovare questo equilibrio.
def find_median_sorted_arrays(nums1, nums2):
# Ensure nums1 is the shorter array
if len(nums1) > len(nums2):
return find_median_sorted_arrays(nums2, nums1)
m, n = len(nums1), len(nums2)
lo, hi = 0, m
while lo <= hi:
i = (lo + hi) // 2 # partition index in nums1
j = (m + n + 1) // 2 - i # partition index in nums2
# Boundary values with sentinels
max_left1 = float('-inf') if i == 0 else nums1[i-1]
min_right1 = float('inf') if i == m else nums1[i]
max_left2 = float('-inf') if j == 0 else nums2[j-1]
min_right2 = float('inf') if j == n else nums2[j]
if max_left1 <= min_right2 and max_left2 <= min_right1:
# Found the correct partition
if (m + n) % 2 == 1:
return float(max(max_left1, max_left2))
return (max(max_left1, max_left2) + min(min_right1, min_right2)) / 2.0
elif max_left1 > min_right2:
hi = i - 1 # i is too large, move left
else:
lo = i + 1 # i is too small, move right
return 0.0
print(find_median_sorted_arrays([1,3],[2])) # 2.0
print(find_median_sorted_arrays([1,2],[3,4])) # 2.5Tracciare la ricerca binaria
Tracciamo nums1=[1,3], nums2=[2]: m=2, n=1, totale=3, lo=0, hi=2. i=(0+2)//2=1, j=(2+1+1)//2-1=1. max_left1=nums1[0]=1, min_right1=nums1[1]=3, max_left2=nums2[0]=2, min_right2=inf (j=1=n). Verifica: 1≤inf e 2≤3 ✓. Totale dispari: restituisce max(1,2)=2.0. ✓ L'algoritmo ha trovato la partizione al primo passaggio perché le dimensioni degli array sono ridotte.
def find_median_traced(nums1, nums2):
if len(nums1) > len(nums2):
return find_median_traced(nums2, nums1)
m, n = len(nums1), len(nums2)
lo, hi = 0, m
step = 0
while lo <= hi:
step += 1
i = (lo + hi) // 2
j = (m + n + 1) // 2 - i
ml1 = float('-inf') if i==0 else nums1[i-1]
mr1 = float('inf') if i==m else nums1[i]
ml2 = float('-inf') if j==0 else nums2[j-1]
mr2 = float('inf') if j==n else nums2[j]
print(f'Step {step}: i={i},j={j}, ml1={ml1},mr1={mr1},ml2={ml2},mr2={mr2}')
if ml1<=mr2 and ml2<=mr1:
if (m+n)%2==1: return float(max(ml1,ml2))
return (max(ml1,ml2)+min(mr1,mr2))/2.0
elif ml1>mr2: hi=i-1
else: lo=i+1
return 0.0
print(find_median_traced([1,3],[2]))Perché cercare nell'array più corto
Si esegue la ricerca binaria sull'array più corto per ottenere O(log(min(m,n))), invece di O(log(m+n)). La partizione dell'array più lungo è completamente determinata dalla partizione di quello più corto. Scambiando gli input quando len(nums1) > len(nums2), l'array più corto è sempre lo spazio di ricerca. L'invariante è che, quando j deriva da i e dalla lunghezza totale, j è sempre un indice di partizione valido per nums2.
# Prove j is always valid:
# Total elements in left halves = (m+n+1)//2
# Left from nums1: i elements (0 <= i <= m)
# Left from nums2: j = (m+n+1)//2 - i elements
# j must be in [0, n]:
# j >= 0: i <= (m+n+1)//2 <= (m+n+1)//2 ≤ ... always true for valid lo/hi
# j <= n: i >= (m+n+1)//2 - n = (m-n+1)//2 >= 0 (since m <= n)
m, n = 3, 5 # m <= n
half = (m+n+1)//2
for i in range(m+1):
j = half - i
valid = 0 <= j <= n
print(f'i={i}: j={j}, valid={valid}')Gestire lunghezze totali pari e dispari
Quando la lunghezza combinata è dispari: la mediana è il massimo delle metà a sinistra (max(max_left1, max_left2)). Quando è pari: la mediana è la media tra il massimo delle metà a sinistra e il minimo delle metà a destra. La formula (m+n+1)//2 per la dimensione della metà a sinistra funziona in entrambi i casi: per una lunghezza totale pari restituisce n//2 (con un elemento in più a sinistra), e si calcola la media con min_right per ottenere la mediana nel caso pari.
def median_demo(a, b):
merged = sorted(a + b)
L = len(merged)
expected = merged[L//2] if L%2==1 else (merged[L//2-1]+merged[L//2])/2
computed = find_median_sorted_arrays(a[:], b[:])
print(f'a={a}, b={b}: merged={merged}, median={expected}, computed={computed}')
assert abs(expected - computed) < 1e-9
def find_median_sorted_arrays(nums1, nums2):
if len(nums1)>len(nums2): return find_median_sorted_arrays(nums2,nums1)
m,n=len(nums1),len(nums2); lo,hi=0,m
while lo<=hi:
i=(lo+hi)//2; j=(m+n+1)//2-i
ml1=float('-inf') if i==0 else nums1[i-1]; mr1=float('inf') if i==m else nums1[i]
ml2=float('-inf') if j==0 else nums2[j-1]; mr2=float('inf') if j==n else nums2[j]
if ml1<=mr2 and ml2<=mr1:
if (m+n)%2==1: return float(max(ml1,ml2))
return (max(ml1,ml2)+min(mr1,mr2))/2.0
elif ml1>mr2: hi=i-1
else: lo=i+1
return 0.0
median_demo([1,3],[2])
median_demo([1,2],[3,4])
median_demo([],[1])
median_demo([2],[]) # single arrayCasi limite
Casi limite fondamentali: (1) un array è vuoto: la mediana dell'array non vuoto; (2) tutti gli elementi di un array sono minori di quelli dell'altro: la partizione si trova a un estremo; (3) elementi duplicati: l'algoritmo li gestisce naturalmente; (4) entrambi gli array hanno lunghezza 1: semplice mediana di due elementi. Dopo aver scritto il codice, verifichi sempre questi casi. I valori sentinella -∞ e +∞ gestiscono correttamente le partizioni ai confini (i=0 o i=m).
def fmsa(a,b):
if len(a)>len(b): return fmsa(b,a)
m,n=len(a),len(b); lo,hi=0,m
while lo<=hi:
i=(lo+hi)//2; j=(m+n+1)//2-i
ml1=float('-inf') if i==0 else a[i-1]; mr1=float('inf') if i==m else a[i]
ml2=float('-inf') if j==0 else b[j-1]; mr2=float('inf') if j==n else b[j]
if ml1<=mr2 and ml2<=mr1:
if (m+n)%2==1: return float(max(ml1,ml2))
return (max(ml1,ml2)+min(mr1,mr2))/2.0
elif ml1>mr2: hi=i-1
else: lo=i+1
# Edge cases
print(fmsa([], [1])) # 1.0
print(fmsa([2], [])) # 2.0
print(fmsa([1,2], [3,4])) # 2.5
print(fmsa([3,4], [1,2])) # 2.5
print(fmsa([1,1,1], [1,1])) # 1.0 (duplicates)
print(fmsa([10,20,30],[5,15,25,35])) # 17.5Generalizzazione: k-esimo elemento più piccolo in due array
Il problema della mediana si generalizza alla ricerca del k-esimo elemento più piccolo nei due array ordinati. A ogni passaggio, si confronta l'elemento in posizione k//2 di ciascun array. Si elimina la metà più piccola: questi k//2 elementi sono tutti più piccoli del k-esimo elemento, quindi possono essere scartati. Si riduce k di k//2 e si procede ricorsivamente. Casi base: un array vuoto (si restituisce il k-esimo elemento dell'array rimanente) oppure k=1 (si restituisce il minimo tra i primi elementi dei due array). Tempo: O(log k) = O(log(m+n)).
def kth_smallest(nums1, nums2, k):
if not nums1: return nums2[k-1]
if not nums2: return nums1[k-1]
if k == 1: return min(nums1[0], nums2[0])
# Compare k//2-th elements
half = k // 2
i = min(half, len(nums1)) - 1 # index in nums1
j = min(half, len(nums2)) - 1 # index in nums2
if nums1[i] <= nums2[j]:
# Eliminate first (i+1) elements of nums1
return kth_smallest(nums1[i+1:], nums2, k - (i+1))
else:
return kth_smallest(nums1, nums2[j+1:], k - (j+1))
nums1, nums2 = [1,3,5,7], [2,4,6,8]
for k in range(1, 9):
print(f'k={k}: {kth_smallest(nums1[:], nums2[:], k)}')Confronto tra tutti gli approcci
Confronto finale: Fusione degli array: tempo O(m+n), spazio O(m+n). Ricerca binaria sulla partizione: tempo O(log(min(m,n))), spazio O(1). Ricorsione per il k-esimo elemento più piccolo: tempo O(log(m+n)), stack delle chiamate O(log k). Il metodo della partizione con ricerca binaria è quello che gli intervistatori si aspettano per questo problema. È il problema comune più difficile di LeetCode da spiegare con chiarezza: si eserciti sulla logica della partizione e sui quattro controlli dei limiti finché non diventano automatici.
# Performance comparison
import time, random
def merge_median(a, b):
merged = sorted(a+b)
L=len(merged)
return merged[L//2] if L%2==1 else (merged[L//2-1]+merged[L//2])/2
def binary_median(a, b):
if len(a)>len(b): return binary_median(b,a)
m,n=len(a),len(b);lo,hi=0,m
while lo<=hi:
i=(lo+hi)//2;j=(m+n+1)//2-i
ml1=float('-inf') if i==0 else a[i-1];mr1=float('inf') if i==m else a[i]
ml2=float('-inf') if j==0 else b[j-1];mr2=float('inf') if j==n else b[j]
if ml1<=mr2 and ml2<=mr1:
if (m+n)%2==1: return float(max(ml1,ml2))
return (max(ml1,ml2)+min(mr1,mr2))/2.0
elif ml1>mr2: hi=i-1
else: lo=i+1
for size in [100, 10000]:
a = sorted(random.sample(range(size*2), size))
b = sorted(random.sample(range(size*2), size))
t1=time.time(); [merge_median(a,b) for _ in range(1000)]; t1=time.time()-t1
t2=time.time(); [binary_median(a,b) for _ in range(1000)]; t2=time.time()-t2
print(f'n={size}: merge={t1:.4f}s, binary={t2:.4f}s, speedup={t1/t2:.1f}x')Strategia di comunicazione durante il colloquio tecnico
Per questo problema difficile durante un colloquio: (1) dichiari subito l'approccio ingenuo della fusione in O(m+n): dimostra competenza. (2) Spieghi l'obiettivo O(log(min(m,n))) e l'idea della partizione. (3) Illustri l'invariante della partizione: max_left1 ≤ min_right2 e max_left2 ≤ min_right1. (4) Gestisca esplicitamente i valori sentinella. (5) Esponga la formula della mediana per i casi dispari e pari. (6) Verifichi con 1-2 esempi. Questa struttura in 5 passaggi dimostra capacità di risolvere i problemi in modo sistematico, anche con un problema che pochi candidati riescono a risolvere perfettamente sotto pressione.
# Clean final solution for interviews:
def findMedianSortedArrays(nums1, nums2):
if len(nums1) > len(nums2):
return findMedianSortedArrays(nums2, nums1)
m, n = len(nums1), len(nums2)
lo, hi = 0, m
while lo <= hi:
i = (lo + hi) // 2
j = (m + n + 1) // 2 - i
max_l1 = nums1[i-1] if i > 0 else float('-inf')
min_r1 = nums1[i] if i < m else float('inf')
max_l2 = nums2[j-1] if j > 0 else float('-inf')
min_r2 = nums2[j] if j < n else float('inf')
if max_l1 <= min_r2 and max_l2 <= min_r1:
if (m + n) % 2:
return float(max(max_l1, max_l2))
return (max(max_l1, max_l2) + min(min_r1, min_r2)) / 2.0
elif max_l1 > min_r2: hi = i - 1
else: lo = i + 1
# Time: O(log(min(m,n))), Space: O(1)
print(findMedianSortedArrays([1,3],[2])) # 2.0
print(findMedianSortedArrays([1,2],[3,4])) # 2.5Verifica rapida
Verifichi la Sua comprensione dei concetti di Data Structures & Algorithms — Coding Interview Prep trattati in questa lezione.
Riepilogo della lezione
In questa lezione ha imparato che: la mediana di due array ordinati può essere trovata in O(log(min(m,n))) cercando con la ricerca binaria il limite di partizione corretto nell'array più corto, la partizione è valida quando max_left1 ≤ min_right2 e max_left2 ≤ min_right1, con valori sentinella per gestire i casi limite e la generalizzazione al k-esimo elemento più piccolo usa un approccio ricorsivo di eliminazione della metà in O(log k). Congratulazioni per aver completato le lezioni sul divide et impera: ora dispone di un kit completo di strumenti per i colloqui di programmazione!
Domande Frequenti
La lezione «Mediana di due array ordinati» è gratuita?
Sì — il testo completo di «Mediana di due array ordinati» è gratuito qui sul web. Per esercitarvi in modo interattivo (un editor di codice integrato e un tutor IA 24/7) e sbloccare il resto del corso DSA Interview Prep, passa a CoddyKit PRO. Il corso DSA Interview Prep include 4 lezioni in totale.
Cosa imparerò in «Mediana di due array ordinati»?
Risolva il problema median-of-two-sorted-arrays in O(log(min(m,n))) usando la ricerca binaria sul confine della partizione dell'array più corto. Eserciti DSA Interview Prep con codice pratico che esegui direttamente nel browser, e un tutor IA 24/7 risponde alle tue domande mentre lavori sulla lezione.
Ho bisogno di esperienza per iniziare DSA Interview Prep?
Non è richiesta alcuna esperienza precedente. DSA Interview Prep su CoddyKit è strutturato per principianti e studenti avanzati, quindi puoi iniziare da qui o dall'inizio e procedere al tuo ritmo. Questa è la lezione 4 di 4.
Quanto tempo richiede la lezione «Mediana di due array ordinati»?
La maggior parte delle lezioni CoddyKit richiede circa 5–10 minuti. Ogni lezione è breve e interattiva, quindi fai progressi costanti e riprendi esattamente da dove hai lasciato su web e app.
Posso scrivere ed eseguire codice in questa lezione DSA Interview Prep?
Sì. Ogni lezione DSA Interview Prep include un editor di codice integrato, quindi scrivi ed esegui codice reale direttamente nel tuo browser e ricevi feedback istantaneo dall'IA — nessuna configurazione locale necessaria.
Tutte le lezioni di questo corso
- Schema divide et impera
- Conteggio delle inversioni con merge sort modificato
- Elemento maggioritario: voto di Boyer-Moore
- Mediana di due array ordinati