Forberedelse til kodeintervjuer · leksjon

Medianen av to sorterte tabeller

Løs «median-of-two-sorted-arrays» i O(log(min(m,n))) ved å bruke binærsøk på partisjonsgrensen i den korteste tabellen.

Leksjon 4 av 413 trinn

Medianen av to sorterte tabeller er en gratis leksjon i Forberedelse til kodeintervjuer på CoddyKit. Dette er leksjon 4 av 4. Du kan lese hele leksjonen gratis nedenfor – og deretter øve praktisk i nettleseren med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt. Den er en del av læringsløpet i Forberedelse til kodeintervjuer, og fremdriften din synkroniseres mellom nettet og CoddyKit-appen. Kurset i Forberedelse til kodeintervjuer inneholder totalt 4 leksjoner.

Medianen til to sorterte arrayer

Medianen til to sorterte arrayer (LeetCode 4) er et klassisk vanskelig problem. Gitt to sorterte arrayer nums1 (lengde m) og nums2 (lengde n) skal du finne medianen i den kombinerte, sorterte sekvensen på O(log(min(m,n)))-tid. En naiv tilnærming fletter begge arrayene på O(m+n), men den optimale løsningen bruker binærsøk på partisjonsgrensene. Dette er et av de vanskeligste problemene som oftest stilles hos ledende teknologiselskaper.

# 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))

Naiv fletting

Den enkleste O(m+n)-tilnærmingen: Flett begge sorterte arrayer, og finn deretter medianen. Fletting av to sorterte arrayer har kompleksiteten O(m+n). Medianen i et array med lengde L er arr[L//2] hvis L er oddetall, eller (arr[L//2-1] + arr[L//2]) / 2 hvis L er partall. Dette er korrekt, men oppfyller ikke kravet om O(log(min(m,n))). Presenter alltid denne metoden først i et intervju for å etablere et utgangspunkt, og optimaliser deretter.

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.5

Partisjonsideen

Nøkkelinnsikten er at medianen deler det kombinerte arrayet i to like store halvdeler. Vi må finne en partisjon av nums1 og en partisjon av nums2 slik at: (1) Venstrehalvdelene har samme totale størrelse som høyrehalvdelene. (2) Alle elementene i venstrehalvdelene er ≤ alle elementene i høyrehalvdelene. Hvis vi utfører binærsøk etter riktig partisjonspunkt i nums1, bestemmes partisjonen i nums2 automatisk av kravet til total lengde.

# 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ærsøk på partisjonen

Utfør binærsøk på partisjonsindeksen i i nums1 (det kortere arrayet). Partisjonsindeksen j i nums2 bestemmes som j = (m+n+1)//2 - i (slik at venstrehalvdelene har (m+n+1)//2 elementer). Partisjonen er gyldig når nums1[i-1] ≤ nums2[j] og nums2[j-1] ≤ nums1[i]. Binærsøket justerer i opp eller ned for å finne denne balansen.

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

Sporing av binærsøket

Følg 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). Kontroller: 1≤inf og 2≤3 ✓. Totallengden er et oddetall: returner max(1,2)=2.0. ✓ Algoritmen fant partisjonen i første trinn fordi arrayene er små.

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]))

Hvorfor binærsøket utføres på det kortere arrayet

Vi utfører binærsøk på det kortere arrayet for å oppnå O(log(min(m,n))) i stedet for O(log(m+n)). Partisjonen i det lengre arrayet bestemmes fullstendig av partisjonen i det kortere. Bytting av input når len(nums1) > len(nums2) sikrer at det kortere arrayet alltid er søkeområdet. Invarianten er at når j utledes fra i og totallengden, er j alltid en gyldig partisjonsindeks for 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}')

Håndtering av partallige og oddetallige totale lengder

Når den samlede lengden er et oddetall: Medianen er det største elementet i venstrehalvdelene (max(max_left1, max_left2)). Når lengden er et partall: Medianen er gjennomsnittet av det største elementet i venstrehalvdelene og det minste elementet i høyrehalvdelene. Formelen (m+n+1)//2 for størrelsen på venstresiden fungerer for begge: For en partallig totallengde gir den n//2 (ett ekstra element på venstresiden), og vi tar gjennomsnittet med min_right for å få medianen ved partall.

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 array

Spesialtilfeller

Kritiske spesialtilfeller: (1) Det ene arrayet er tomt – medianen i det ikke-tomme arrayet. (2) Alle elementene i det ene arrayet er mindre enn elementene i det andre – partisjonen går helt til den ene ytterkanten. (3) Duplikate elementer – algoritmen håndterer dem naturlig. (4) Begge arrayene har lengde 1 – enkel median for to elementer. Test alltid disse tilfellene etter at du har skrevet koden. Sentinelverdiene -∞ og +∞ håndterer partisjoner ved grensene (i=0 eller i=m) på en ryddig måte.

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.5

Generalisering: det k-te minste elementet i to arrayer

Medianproblemet kan generaliseres til å finne det k-te minste elementet i to sorterte arrayer. Ved hvert trinn sammenligner du det k//2-te elementet i hvert array. Fjern den minste halvdelen: Disse k//2 elementene er alle mindre enn det k-te elementet, så vi kan forkaste dem. Reduser k med k//2 og fortsett rekursivt. Basistilfeller: Det ene arrayet er tomt (returner det k-te elementet i det gjenværende arrayet), eller k=1 (returner minimum av de to første elementene). Tid: 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)}')

Sammenligning av alle metodene

Endelig sammenligning: Slå sammen arrayer: O(m+n) tid, O(m+n) plass. Binærsøk på partisjon: O(log(min(m,n))) tid, O(1) plass. Rekursjon for k-te minste: O(log(m+n)) tid, O(log k) kallstakk. Metoden med binærsøk på partisjon er den intervjuerne forventer for dette problemet. Det er det vanskeligste vanlige LeetCode-problemet å forklare tydelig – øv på partisjonslogikken og de fire grensekontrollene til de sitter automatisk.

# 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')

Strategi for kommunikasjon i intervjuer

For dette vanskelige problemet i et intervju: (1) Presenter straks den naive O(m+n)-tilnærmingen med sammenslåing – det viser kompetanse. (2) Forklar målet O(log(min(m,n))) og partisjonsideen. (3) Gå gjennom partisjonsinvarianten: max_left1 ≤ min_right2 og max_left2 ≤ min_right1. (4) Håndter vaktverdier eksplisitt. (5) Oppgi medianformelen for oddetall og partall. (6) Test med 1–2 eksempler. Dette rammeverket i fem trinn viser systematisk problemløsning, selv for et problem som få kandidater løser perfekt under press.

# 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.5

Hurtigsjekk

Test forståelsen din av konseptene i Data Structures & Algorithms — Coding Interview Prep fra denne leksjonen.

Besvar den i den interaktive leksjonen

Oppsummering av leksjonen

I denne leksjonen lærte du at medianen til to sorterte arrayer kan finnes på O(log(min(m,n))) ved å bruke binærsøk for å finne den riktige partisjonsgrensen i den korteste arrayen, at partisjonen er gyldig når max_left1 ≤ min_right2 og max_left2 ≤ min_right1, med vaktverdier som håndterer grensetilfeller, og at generaliseringen til den k-te minste bruker en rekursiv tilnærming som eliminerer halvparten i hvert trinn, på O(log k) tid. Gratulerer med å ha fullført leksjonene om del-og-hersk – nå har du et omfattende verktøysett for kodeintervjuer!

Gratis å komme i gang

Lær deg Forberedelse til kodeintervjuer med en AI-veileder – gratis

Skriv og kjør ekte kode i nettleseren, få umiddelbar hjelp fra en AI-veileder som er tilgjengelig døgnet rundt, og fortsett der du slapp – på nettet eller i appen.

Kurs: 90
Leksjoner: 360

Start læringen gratis Se hele kurset

Ofte stilte spørsmål

Er leksjonen «Medianen av to sorterte tabeller» gratis?

Ja – hele teksten i «Medianen av to sorterte tabeller» er gratis å lese her på nettet. For å øve interaktivt med en innebygd kodeeditor og en AI-veileder som er tilgjengelig døgnet rundt, og for å låse opp resten av Forberedelse til kodeintervjuer-kurset, kan du oppgradere til CoddyKit PRO. Kurset i Forberedelse til kodeintervjuer inneholder totalt 4 leksjoner.

Hva lærer jeg i «Medianen av to sorterte tabeller»?

Løs «median-of-two-sorted-arrays» i O(log(min(m,n))) ved å bruke binærsøk på partisjonsgrensen i den korteste tabellen. Du øver på Forberedelse til kodeintervjuer med praktisk kode som du kjører direkte i nettleseren, mens en AI-veileder som er tilgjengelig døgnet rundt, svarer på spørsmålene dine mens du jobber deg gjennom leksjonen.

Trenger jeg erfaring for å begynne med Forberedelse til kodeintervjuer?

Ingen tidligere erfaring er nødvendig. Forberedelse til kodeintervjuer på CoddyKit er lagt opp for både nybegynnere og viderekomne, så De kan begynne her eller helt fra start og lære i Deres eget tempo. Dette er leksjon 4 av 4.

Hvor lang tid tar leksjonen «Medianen av to sorterte tabeller»?

De fleste CoddyKit-leksjoner tar omtrent 5–10 minutter. Hver leksjon er kort og interaktiv, slik at De gjør jevne fremskritt og kan fortsette akkurat der De slapp – både på nettet og i appen.

Kan jeg skrive og kjøre kode i denne Forberedelse til kodeintervjuer-leksjonen?

Ja. Alle Forberedelse til kodeintervjuer-leksjoner har en innebygd kodeeditor, slik at De kan skrive og kjøre ekte kode direkte i nettleseren og få umiddelbar tilbakemelding fra AI – uten lokal konfigurering.

Alle leksjonene i dette kurset

Mal for splitt og hersk
Tell inversjoner med modifisert flettesortering
Majoritetselement: Boyer-Moore-avstemning
Medianen av to sorterte tabeller

← Tilbake til Forberedelse til kodeintervjuer