Mediana dwóch posortowanych tablic
Rozwiązywać problem median-of-two-sorted-arrays w czasie O(log(min(m,n))) za pomocą wyszukiwania binarnego granicy podziału krótszej tablicy
Mediana dwóch posortowanych tablic to bezpłatna lekcja DSA Interview Prep na CoddyKit. To lekcja 4 z 4. Możesz przeczytać całą lekcję poniżej za darmo — a potem ćwiczyć ją interaktywnie w przeglądarce z wbudowanym edytorem kodu i tutorem AI dostępnym 24/7. To część ścieżki edukacyjnej DSA Interview Prep, a Twój postęp synchronizuje się między webem a aplikacją CoddyKit. Kurs DSA Interview Prep zawiera 4 lekcji w sumie.
Mediana dwóch posortowanych tablic
Mediana dwóch posortowanych tablic (LeetCode 4) to klasyczny trudny problem. Dla dwóch posortowanych tablic nums1 (długości m) i nums2 (długości n) należy znaleźć medianę ich połączonej, posortowanej sekwencji w czasie O(log(min(m,n))). Naiwne podejście scala obie tablice w czasie O(m+n), ale optymalne rozwiązanie wykorzystuje wyszukiwanie binarne na granicach podziału. To jeden z najczęściej zadawanych trudnych problemów w czołowych firmach technologicznych.
# 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))Naiwne podejście ze scalaniem
Najprostsze podejście O(m+n): scal obie posortowane tablice, a następnie znajdź medianę. Scalanie dwóch posortowanych tablic ma złożoność O(m+n). Mediana tablicy długości L wynosi arr[L//2], jeśli L jest nieparzyste, lub (arr[L//2-1] + arr[L//2]) / 2, jeśli L jest parzyste. Jest to rozwiązanie poprawne, ale nie spełnia wymagania O(log(min(m,n))). Na rozmowie kwalifikacyjnej zawsze należy przedstawić je najpierw, aby ustalić punkt odniesienia, a następnie zaprezentować rozwiązanie zoptymalizowane.
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.5Idea podziału
Kluczowa obserwacja: mediana dzieli połączoną tablicę na dwie równe połowy. Należy znaleźć podział nums1 i podział nums2 takie, że: (1) Lewe połowy mają łącznie tyle samo elementów co prawe połowy. (2) Wszystkie elementy w lewych połowach są ≤ wszystkim elementom w prawych połowach. Jeśli zastosujemy wyszukiwanie binarne do znalezienia właściwej pozycji podziału w nums1, pozycja podziału w nums2 zostanie automatycznie wyznaczona na podstawie ograniczenia dotyczącego łącznej długości.
# 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])Wyszukiwanie binarne granicy podziału
Wykonujemy wyszukiwanie binarne indeksu podziału i w nums1 (krótszej tablicy). Indeks podziału j w nums2 jest wyznaczany jako j = (m+n+1)//2 - i (dzięki czemu lewe połowy mają (m+n+1)//2 elementów). Podział jest poprawny, gdy nums1[i-1] ≤ nums2[j] oraz nums2[j-1] ≤ nums1[i]. Wyszukiwanie binarne zwiększa lub zmniejsza i, aby znaleźć równowagę.
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.5Śledzenie przebiegu wyszukiwania binarnego
Prześledźmy 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). Sprawdzenie: 1≤inf oraz 2≤3 ✓. Długość całkowita jest nieparzysta: zwracamy max(1,2)=2.0. ✓ Algorytm znalazł podział w pierwszym kroku, ponieważ rozmiary tablic są małe.
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]))Dlaczego wyszukiwanie binarne wykonuje się w krótszej tablicy
Wykonujemy wyszukiwanie binarne w krótszej tablicy, aby osiągnąć O(log(min(m,n))) zamiast O(log(m+n)). Podział dłuższej tablicy jest w pełni wyznaczony przez podział krótszej. Zamiana danych wejściowych, gdy len(nums1) > len(nums2), gwarantuje, że krótsza tablica zawsze jest przestrzenią wyszukiwania. Niezmiennik: gdy j jest wyznaczane na podstawie i i łącznej długości, j zawsze jest poprawnym indeksem podziału dla 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}')Obsługa łącznej długości parzystej i nieparzystej
Gdy łączna długość jest nieparzysta: mediana jest maksimum z lewych połówek (max(max_left1, max_left2)). Gdy jest parzysta: mediana jest średnią maksimum z lewych połówek i minimum z prawych połówek. Wzór (m+n+1)//2 na rozmiar lewej połowy działa w obu przypadkach: dla parzystej długości daje n//2 (jeden dodatkowy element po lewej), a następnie uśredniamy tę wartość z min_right, aby uzyskać medianę dla parzystej długości.
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 arrayPrzypadki brzegowe
Kluczowe przypadki brzegowe: (1) Jedna tablica jest pusta — mediana niepustej tablicy. (2) Wszystkie elementy jednej tablicy są mniejsze od elementów drugiej — podział znajduje się na jednym z krańców. (3) Powtarzające się elementy — algorytm obsługuje je bez dodatkowych modyfikacji. (4) Obie tablice mają długość 1 — prosta mediana dwóch elementów. Zawsze należy przetestować te przypadki po napisaniu kodu. Wartości wartownikowe -∞ i +∞ poprawnie obsługują podziały na granicach (i=0 lub 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.5Uogólnienie: k-ty najmniejszy element w dwóch tablicach
Problem mediany można uogólnić do znajdowania k-tego najmniejszego elementu w dwóch posortowanych tablicach. W każdym kroku porównujemy element znajdujący się na pozycji k//2 w każdej tablicy. Odrzucamy mniejszą połowę: te k//2 elementów jest na pewno mniejszych od k-tego elementu, więc możemy je pominąć. Zmniejszamy k o k//2 i rekurencyjnie powtarzamy operację. Przypadki bazowe: jedna tablica jest pusta (zwracamy k-ty element z pozostałej) lub k=1 (zwracamy mniejszą z obu pierwszych wartości). Czas: 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)}')Porównanie wszystkich podejść
Ostateczne porównanie: scalanie tablic: czas O(m+n), pamięć O(m+n). Wyszukiwanie binarne po podziale: czas O(log(min(m,n))), pamięć O(1). Rekurencja dla k-tego najmniejszego elementu: czas O(log(m+n)), stos wywołań O(log k). Metoda wyszukiwania binarnego z podziałem jest tą, której rekruterzy oczekują w tym zadaniu. To najtrudniejsze często spotykane zadanie LeetCode do jasnego wyjaśnienia — proszę ćwiczyć logikę podziału i cztery kontrole wartości granicznych, aż ich wykonywanie stanie się automatyczne.
# 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 komunikacji podczas rozmowy kwalifikacyjnej
W przypadku tego trudnego zadania podczas rozmowy kwalifikacyjnej: (1) natychmiast proszę przedstawić naiwne podejście polegające na scalaniu w czasie O(m+n) — pokazuje ono kompetencje. (2) Proszę wyjaśnić cel O(log(min(m,n))) i ideę podziału. (3) Proszę prześledzić niezmiennik podziału: max_left1 ≤ min_right2 oraz max_left2 ≤ min_right1. (4) Proszę jawnie obsłużyć wartości wartownicze. (5) Proszę podać wzór na medianę dla nieparzystej i parzystej liczby elementów. (6) Proszę przetestować rozwiązanie na 1–2 przykładach. Ten pięciostopniowy schemat pokazuje systematyczne rozwiązywanie problemów nawet w przypadku zadania, którego niewielu kandydatów potrafi perfekcyjnie rozwiązać pod presją.
# 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.5Szybkie sprawdzenie
Sprawdź swoje zrozumienie zagadnień Data Structures & Algorithms — Coding Interview Prep z tej lekcji.
Podsumowanie lekcji
W tej lekcji nauczyłeś się, że: medianę dwóch posortowanych tablic można znaleźć w czasie O(log(min(m,n))) za pomocą wyszukiwania binarnego właściwej granicy podziału w krótszej tablicy, podział jest prawidłowy, gdy max_left1 ≤ min_right2 oraz max_left2 ≤ min_right1, a wartości wartownicze obsługują przypadki graniczne, a także że uogólnienie na k-ty najmniejszy element wykorzystuje rekurencyjne eliminowanie połowy danych w czasie O(log k). Gratulacje z okazji ukończenia lekcji o metodzie dziel i zwyciężaj — masz teraz wszechstronny zestaw narzędzi przydatnych podczas rozmów kwalifikacyjnych dotyczących programowania!
Często zadawane pytania
Czy lekcja „Mediana dwóch posortowanych tablic” jest bezpłatna?
Tak — pełny tekst „Mediana dwóch posortowanych tablic” jest dostępny za darmo tutaj w sieci. Aby ćwiczyć ją interaktywnie (wbudowany edytor kodu i tutor AI dostępny 24/7) i odblokować resztę kursu DSA Interview Prep, przejdź na CoddyKit PRO. Kurs DSA Interview Prep zawiera 4 lekcji w sumie.
Co nauczysz się w „Mediana dwóch posortowanych tablic”?
Rozwiązywać problem median-of-two-sorted-arrays w czasie O(log(min(m,n))) za pomocą wyszukiwania binarnego granicy podziału krótszej tablicy Ćwiczysz DSA Interview Prep z praktycznym kodem, który uruchamiasz bezpośrednio w przeglądarce, a tutor AI dostępny 24/7 odpowiada na Twoje pytania podczas pracy nad lekcją.
Czy potrzebuję doświadczenia, aby zacząć DSA Interview Prep?
Nie wymagamy żadnego doświadczenia. DSA Interview Prep w CoddyKit jest strukturyzowany dla początkujących i zaawansowanych użytkowników, więc możesz zacząć tutaj lub od początku i uczyć się w swoim tempie. To lekcja 4 z 4.
Ile czasu zajmuje lekcja „Mediana dwóch posortowanych tablic”?
Większość lekcji CoddyKit trwa około 5–10 minut. Każda lekcja to mały, interaktywny krok, dzięki czemu robisz systematyczne postępy i zawsze wracasz dokładnie do tego samego miejsca — na webie i w aplikacji.
Czy mogę pisać i uruchamiać kod w tej lekcji DSA Interview Prep?
Tak. Każda lekcja DSA Interview Prep zawiera wbudowany edytor kodu, więc piszesz i uruchamiasz prawdziwy kod bezpośrednio w przeglądarce i od razu otrzymujesz sprzężenie zwrotne od AI — bez konfiguracji na komputerze.
Wszystkie lekcje w tym kursie
- Schemat dziel i zwyciężaj
- Zliczanie inwersji za pomocą zmodyfikowanego sortowania przez scalanie
- Element większościowy: głosowanie Boyera-Moore’a
- Mediana dwóch posortowanych tablic