Kahden järjestetyn taulukon mediaani
Ratkaiskaa median-of-two-sorted-arrays ajassa O(log(min(m,n))) tekemällä binäärihaku lyhyemmän taulukon osion rajalla.
Kahden järjestetyn taulukon mediaani on ilmainen Valmistautuminen ohjelmointihaastatteluihin-oppitunti CoddyKitissä. Tämä on oppitunti 4/4. Voit lukea koko oppitunnin alta ilmaiseksi ja harjoitella sen jälkeen käytännössä selaimessa sisäänrakennetulla koodieditorilla ja ympäri vuorokauden käytettävissä olevan tekoälytuutorin avulla. Oppitunti kuuluu Valmistautuminen ohjelmointihaastatteluihin-oppimispolkuun, ja edistymisesi synkronoituu verkon ja CoddyKit-sovelluksen välillä. Valmistautuminen ohjelmointihaastatteluihin-kurssilla on yhteensä 4 oppituntia.
Kahden lajitellun taulukon mediaani
Kahden lajitellun taulukon mediaani (LeetCode 4) on klassinen haastava ongelma. Annettuina ovat kaksi lajiteltua taulukkoa, nums1 (pituus m) ja nums2 (pituus n), ja tehtävänä on löytää niiden yhdistetyn lajitellun jonon mediaani ajassa O(log(min(m,n))). Naiivi ratkaisu yhdistää molemmat taulukot ajassa O(m+n), mutta optimaalinen ratkaisu käyttää binäärihakua ositusrajoilla. Tämä on yksi suurten teknologiayritysten useimmin kysymistä vaikeista ongelmista.
# 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))Naiivi yhdistämistapa
Yksinkertaisin O(m+n)-menetelmä: yhdistäkää molemmat lajitellut taulukot ja etsikää sitten mediaani. Kahden lajitellun taulukon yhdistäminen vie ajan O(m+n). L-pituisen taulukon mediaani on arr[L//2], jos L on pariton, tai (arr[L//2-1] + arr[L//2]) / 2, jos L on parillinen. Tämä on oikein, mutta ei täytä vaatimusta O(log(min(m,n))). Esittäkää tämä haastattelussa aina ensin lähtötason määrittämiseksi ja optimoikaa sitten.
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.5Osituksen perusidea
Keskeinen oivallus: mediaani jakaa yhdistetyn taulukon kahteen yhtä suureen puoliskoon. Meidän on löydettävä nums1- ja nums2-taulukoista ositukset, joissa: (1) vasempien puoliskojen yhteenlaskettu koko on sama kuin oikeiden puoliskojen. (2) Kaikki vasempien puoliskojen alkiot ovat ≤ kaikkia oikeiden puoliskojen alkioita. Jos etsimme nums1-taulukon sopivaa osituskohtaa binäärihaulla, nums2-taulukon ositus määräytyy automaattisesti kokonaispituuden rajoitteen perusteella.
# 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])Binäärihaku osituskohdasta
Tehkää binäärihaku nums1-taulukon (lyhyemmän taulukon) ositusindeksistä i. nums2-taulukon ositusindeksi j määräytyy kaavalla j = (m+n+1)//2 - i, mikä varmistaa, että vasemmissa puoliskoissa on (m+n+1)//2 alkiota. Ositus on kelvollinen, kun nums1[i-1] ≤ nums2[j] ja nums2[j-1] ≤ nums1[i]. Binäärihaku siirtää i-indeksiä ylös- tai alaspäin tämän tasapainon löytämiseksi.
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.5Binäärihaun jäljittäminen
Jäljitetään esimerkki nums1=[1,3], nums2=[2]: m=2, n=1, total=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). Tarkistus: 1≤inf ja 2≤3 ✓. Kokonaispituus on pariton: palauta max(1,2)=2.0. ✓ Algoritmi löysi osituksen ensimmäisessä vaiheessa, koska taulukot ovat pieniä.
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]))Miksi binäärihaku tehdään lyhyemmässä taulukossa
Teemme binäärihaun lyhyemmässä taulukossa saavuttaaksemme ajan O(log(min(m,n))) ajan O(log(m+n)) sijaan. Pidemmän taulukon ositus määräytyy täysin lyhyemmän taulukon osituksen perusteella. Syötteiden vaihtaminen, jos len(nums1) > len(nums2), varmistaa, että lyhyempi taulukko on aina hakualueena. Invariantti: kun j johdetaan i-indeksistä ja kokonaispituudesta, j on aina kelvollinen nums2-taulukon ositusindeksi.
# 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}')Parittoman ja parillisen kokonaispituuden käsittely
Kun yhdistetyn taulukon pituus on pariton: mediaani on vasempien puoliskojen maksimi (max(max_left1, max_left2)). Kun pituus on parillinen: mediaani on vasempien puoliskojen maksimin ja oikeiden puoliskojen minimin keskiarvo. Kaava (m+n+1)//2 vasemman puoliskon koolle toimii molemmissa tapauksissa: parillisella kokonaispituudella se antaa n//2 (vasemmalle puolelle yhden ylimääräisen alkion), ja keskiarvo otetaan min_right-arvon kanssa parillisen pituuden mediaanin saamiseksi.
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 arrayReunatapaukset
Keskeiset reunatapaukset: (1) Toinen taulukko on tyhjä — mediaani saadaan ei-tyhjästä taulukosta. (2) Kaikki toisen taulukon alkiot ovat pienempiä kuin toisen — ositus menee toiseen ääripäähän. (3) Duplikaattialkiot — algoritmi käsittelee ne luonnostaan. (4) Molempien taulukoiden pituus on 1 — kyseessä on yksinkertainen kaksialkioisen taulukon mediaani. Testatkaa nämä tapaukset aina koodauksen jälkeen. Sentineliarvot -∞ ja +∞ käsittelevät rajaositukset (i=0 tai i=m) siististi.
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.5Yleistys: k:s pienin alkio kahdesta taulukosta
Mediaaniongelma voidaan yleistää etsimään k:s pienin alkio kahdesta lajitellusta taulukosta. Verratkaa kussakin vaiheessa kummankin taulukon k//2:tta alkiota. Hylätkää pienempi puolisko: nämä k//2 alkiota ovat kaikki pienempiä kuin k:s alkio, joten ne voidaan poistaa. Pienentäkää k-arvoa k//2:lla ja jatkakaa rekursiivisesti. Perustapaukset ovat tyhjä taulukko (palautetaan jäljellä olevan taulukon k:s alkio) tai k=1 (palautetaan molempien taulukoiden etupään pienempi alkio). Aikavaativuus: 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)}')Kaikkien menetelmien vertailu
Lopullinen vertailu: taulukoiden yhdistäminen: aikavaativuus O(m+n), tilavaativuus O(m+n). Binäärihaku osituksen perusteella: aikavaativuus O(log(min(m,n))), tilavaativuus O(1). k:nnen pienimmän alkion rekursio: aikavaativuus O(log(m+n)), kutsupinon tilavaativuus O(log k). Binäärihakuun perustuva ositusmenetelmä on se, jota haastattelijat odottavat tässä tehtävässä. Se on vaikein yleinen LeetCode-tehtävä selittää selkeästi — harjoitelkaa osituslogiikkaa ja neljää rajatarkistusta, kunnes osaatte ne ulkoa.
# 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')Haastattelussa viestimisen strategia
Kun ratkaisette tätä vaikeaa tehtävää haastattelussa: (1) Esittäkää naiivi O(m+n)-aikainen yhdistämisratkaisu heti — se osoittaa osaamista. (2) Selittäkää O(log(min(m,n)))-tavoite ja ositusidea. (3) Käykää läpi osituksen invariantti: max_left1 ≤ min_right2 ja max_left2 ≤ min_right1. (4) Käsitelkää sentineliarvot selkeästi. (5) Esittäkää mediaanikaava parittomalle ja parilliselle määrälle. (6) Testatkaa ratkaisu 1–2 esimerkillä. Tämä viiden kohdan kehys osoittaa järjestelmällistä ongelmanratkaisua, vaikka harvat ehdokkaat ratkaisevat tämän tehtävän täydellisesti paineen alla.
# 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.5Pikatarkistus
Testatkaa ymmärryksenne tämän oppitunnin Data Structures & Algorithms — Coding Interview Prep -käsitteistä.
Oppitunnin yhteenveto
Tässä oppitunnissa opitte, että: kahden järjestetyn taulukon mediaani voidaan löytää ajassa O(log(min(m,n))) etsimällä lyhyemmän taulukon oikeaa ositusrajaa binäärihaulla, ositus on kelvollinen, kun max_left1 ≤ min_right2 ja max_left2 ≤ min_right1, ja rajatapaukset käsitellään sentineliarvoilla sekä k:nnen pienimmän alkion yleistys käyttää rekursiivista puolikkaiden poistamiseen perustuvaa lähestymistapaa ajassa O(log k). Onnittelut Divide and Conquer -oppituntien suorittamisesta — teillä on nyt kattava työkalupakki koodaushaastatteluja varten!
Opi Valmistautuminen ohjelmointihaastatteluihin tekoälytuutorin avulla — ilmaiseksi
Kirjoita ja suorita oikeaa koodia selaimessa, saa välitöntä apua tekoälytuutorilta ympäri vuorokauden ja jatka siitä, mihin jäit, verkossa tai sovelluksessa.
- Kurssit
- 90
- Oppitunnit
- 360
Usein kysytyt kysymykset
Onko oppitunti ”Kahden järjestetyn taulukon mediaani” ilmainen?
Kyllä – oppitunnin ”Kahden järjestetyn taulukon mediaani” koko tekstin voi lukea täällä verkossa ilmaiseksi. Jos haluat harjoitella interaktiivisesti sisäänrakennetulla koodieditorilla ja ympäri vuorokauden käytettävissä olevan tekoälytuutorin avulla sekä avata koko Valmistautuminen ohjelmointihaastatteluihin-kurssin, päivitä CoddyKit PROhon. Valmistautuminen ohjelmointihaastatteluihin-kurssilla on yhteensä 4 oppituntia.
Mitä opin oppitunnilla ”Kahden järjestetyn taulukon mediaani”?
Ratkaiskaa median-of-two-sorted-arrays ajassa O(log(min(m,n))) tekemällä binäärihaku lyhyemmän taulukon osion rajalla. Harjoittelet Valmistautuminen ohjelmointihaastatteluihin-aihetta koodilla, jonka suoritat suoraan selaimessa. Ympäri vuorokauden käytettävissä oleva tekoälytuutori vastaa kysymyksiisi oppitunnin aikana.
Tarvitsenko kokemusta aloittaakseni Valmistautuminen ohjelmointihaastatteluihin-opiskelun?
Aiempi kokemus ei ole tarpeen. CoddyKitin Valmistautuminen ohjelmointihaastatteluihin-oppimispolku sopii vasta-alkajista edistyneisiin, joten voit aloittaa tästä tai alusta ja edetä omaan tahtiisi. Tämä on oppitunti 4/4.
Kuinka kauan ”Kahden järjestetyn taulukon mediaani”-oppitunnin suorittaminen kestää?
Useimmat CoddyKitin oppitunnit kestävät noin 5–10 minuuttia. Jokainen oppitunti on lyhyt ja interaktiivinen, joten edistyt tasaisesti ja voit jatkaa siitä, mihin jäit – sekä verkossa että sovelluksessa.
Voinko kirjoittaa ja suorittaa koodia tällä Valmistautuminen ohjelmointihaastatteluihin-oppitunnilla?
Kyllä. Jokainen Valmistautuminen ohjelmointihaastatteluihin-oppitunti sisältää sisäänrakennetun koodieditorin, joten voit kirjoittaa ja suorittaa oikeaa koodia suoraan selaimessa ja saada välitöntä palautetta tekoälyltä – paikallista asennusta ei tarvita.
Kaikki tämän kurssin oppitunnit
- Hajota ja hallitse -malli
- Inversioiden laskeminen muokatulla merge sort -algoritmilla
- Enemmistöalkio: Boyer-Moore-äänestys
- Kahden järjestetyn taulukon mediaani