Median fra datastrøm og k-veis fletting
Vedlikehold to heaper, en max-heap for den minste halvdelen og en min-heap for den største, for medianoppdateringer i O(log n), og flett k sorterte lister med en heap.
Median fra datastrøm og k-veis fletting 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.
Problemet med median fra en datastrøm
Finn medianen fra en datastrøm (LeetCode #295) ber Dem støtte to operasjoner effektivt: addNum(num) for å legge til et tall og findMedian() for å returnere den gjeldende medianen. Medianen i en liste med partallslengde er gjennomsnittet av de to midterste verdiene. En sortert liste med brute force gir O(n) innsetting og O(1) for å finne medianen. Den optimale løsningen bruker to heap-er for innsetting på O(log n) og median på O(1).
import heapq
# Strategy: maintain two halves of the data
# max_heap: lower half (stores negated values for max behavior)
# min_heap: upper half
# Invariant: len(max_heap) == len(min_heap) or len(max_heap) == len(min_heap) + 1
# Invariant: max(max_heap) <= min(min_heap)
# Median:
# odd count: max_heap[0] (top of lower half)
# even count: average of tops of both halves
print('Two-heap strategy for O(log n) insert, O(1) median')MedianFinder-implementering med to heap-er
Vedlikehold en maks-heap for den nedre halvdelen og en min-heap for den øvre halvdelen. Sørg alltid for at maks-heapen har samme størrelse som, eller ett element mer enn, min-heapen. Når De legger til et tall: legg det i maks-heapen, balanser deretter ved å flytte toppen av maks-heapen til min-heapen hvis toppen er større enn minimumet i min-heapen, og balanser størrelsene på nytt ved behov.
import heapq
class MedianFinder:
def __init__(self):
self.lo = [] # max-heap (negated) for lower half
self.hi = [] # min-heap for upper half
def addNum(self, num):
heapq.heappush(self.lo, -num) # push to lower half
# Ensure max of lower <= min of upper
if self.hi and -self.lo[0] > self.hi[0]:
heapq.heappush(self.hi, -heapq.heappop(self.lo))
# Balance sizes: lo can have at most 1 more than hi
if len(self.lo) > len(self.hi) + 1:
heapq.heappush(self.hi, -heapq.heappop(self.lo))
elif len(self.hi) > len(self.lo):
heapq.heappush(self.lo, -heapq.heappop(self.hi))
def findMedian(self):
if len(self.lo) > len(self.hi):
return -self.lo[0] # odd count: top of lower half
return (-self.lo[0] + self.hi[0]) / 2
mf = MedianFinder()
for n in [1, 2, 3, 4, 5]: mf.addNum(n)
print(mf.findMedian()) # 3.0Følg trinnene i MedianFinder
Det er avgjørende å forstå hvorfor invarianten for to heap-er opprettholdes når løsningen skal forklares i et intervju. Gå trinnvis gjennom innleggingen av [5, 15, 1, 3]. Etter hver innsetting: balanser slik at den nedre maks-heapen inneholder den minste halvdelen. Invarianten sikrer at max(lo) <= min(hi) alltid gjelder, noe som gjør medianen trivielt tilgjengelig på toppen av én eller begge heapene.
import heapq
# Manual trace for [5, 15, 1, 3]:
# add 5: lo=[-5] hi=[] median=5
# add 15: lo=[-5] hi=[15] median=(5+15)/2=10
# add 1: lo=[-5,-1] hi=[15] median=5
# add 3: lo=[-5,-3,-1] hi=[15] -- lo too big
# -> lo=[-5,-3] hi=[1,15] -- wait, wrong direction
# Actually:
# add 1: push to lo -> lo=[-5,-1], then 1>lo? No, -lo[0]=5>15? No
# lo has 2, hi has 1: balance -> move lo top to hi
# lo=[-1], hi=[5,15]
# Median = (-lo[0] + hi[0])/2 = (1+5)/2 = 3
mf2 = MedianFinder()
for n, expected in [(5, 5.0), (15, 10.0), (1, 5.0), (3, 4.0)]:
mf2.addNum(n)
print(f'After adding {n}: median={mf2.findMedian()} (expected ~{expected})')Median for et glidende vindu
Median for et glidende vindu (LeetCode #480) er en vanskeligere variant: finn medianen for hvert vindu med størrelse k når det glir over arrayet. Tilnærmingen med to heap-er utvides med et lazy deletion-sett for å håndtere elementer som glir ut av vinduet. Når et element forlater vinduet, markerer De det i slettesettet. Når det når toppen av en av heapene, forkaster De det.
import heapq
def median_sliding_window(nums, k):
lo = [] # max-heap (negated)
hi = [] # min-heap
removed = {}
result = []
def balance():
# Move valid tops to correct side
while lo and removed.get(-lo[0], 0) > 0:
removed[-lo[0]] -= 1; heapq.heappop(lo)
while hi and removed.get(hi[0], 0) > 0:
removed[hi[0]] -= 1; heapq.heappop(hi)
for i, num in enumerate(nums):
heapq.heappush(lo, -num)
heapq.heappush(hi, -heapq.heappop(lo))
if len(hi) > len(lo): heapq.heappush(lo, -heapq.heappop(hi))
if i >= k:
out = nums[i - k]
removed[out] = removed.get(out, 0) + 1
balance()
if len(lo) > len(hi): heapq.heappush(hi, -heapq.heappop(lo))
if i >= k - 1:
if len(lo) > len(hi): result.append(float(-lo[0]))
else: result.append((-lo[0] + hi[0]) / 2.0)
return result
print(median_sliding_window([1,3,-1,-3,5,3,6,7], 3)) # [1,-1,-1,3,5,6]K-veis fletting: problemet
Fletting av k sorterte lister (LeetCode #23) er et grunnleggende problem med anvendelser innen ekstern sortering, databasesammenslåing og distribuerte systemer. Gitt k sorterte lenkede lister med totalt n noder skal De flette dem til én sortert liste. Den naive metoden (flett to om gangen) har kompleksitet O(kn), eller O(n log k) med del-og-hersk. Heapmetoden behandler hver node nøyaktig én gang med O(log k) arbeid per node: totalt O(n log k).
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
# Build a linked list from a Python list
def build_list(arr):
dummy = ListNode(0)
curr = dummy
for val in arr:
curr.next = ListNode(val)
curr = curr.next
return dummy.next
# Convert linked list to Python list for printing
def to_list(head):
result = []
while head:
result.append(head.val)
head = head.next
return result
print('K-way merge: O(n log k) using a min-heap of k heads')K-veis fletting med en min-heap
Initialiser heapen med den første noden i hver liste. Ved hvert trinn tar De ut minimumet, legger det til resultatet og legger inn neste node fra den listen (hvis det finnes en). Heapen har alltid høyst k elementer – én første node per aktiv liste. Siden vi behandler totalt n noder med O(log k) heap-operasjoner for hver node, er totaltiden O(n log k), og plassforbruket er O(k) for heapen.
import heapq
def merge_k_lists(lists):
dummy = ListNode(0)
curr = dummy
heap = []
for i, node in enumerate(lists):
if node:
heapq.heappush(heap, (node.val, i, node))
while heap:
val, i, node = heapq.heappop(heap)
curr.next = node
curr = curr.next
if node.next:
heapq.heappush(heap, (node.next.val, i, node.next))
return dummy.next
lists = [
build_list([1, 4, 5]),
build_list([1, 3, 4]),
build_list([2, 6])
]
result = merge_k_lists(lists)
print(to_list(result)) # [1, 1, 2, 3, 4, 4, 5, 6]Minste intervall som dekker k lister
Minste intervall (LeetCode #632) finner det minste intervallet [lo, hi] slik at minst ett element fra hver av de k sorterte listene ligger i intervallet. Bruk en min-heap initialisert med det første elementet i hver liste, og hold oversikt over gjeldende maksimum. Gjør intervallet mindre ved alltid å gå videre i listen med gjeldende minimum. Stopp når en liste er tom.
import heapq
def smallest_range(nums):
heap = []
current_max = float('-inf')
for i, lst in enumerate(nums):
heapq.heappush(heap, (lst[0], i, 0))
current_max = max(current_max, lst[0])
best = [float('-inf'), float('inf')]
while heap:
current_min, list_idx, elem_idx = heapq.heappop(heap)
if current_max - current_min < best[1] - best[0]:
best = [current_min, current_max]
if elem_idx + 1 >= len(nums[list_idx]):
break # one list exhausted
next_val = nums[list_idx][elem_idx + 1]
heapq.heappush(heap, (next_val, list_idx, elem_idx + 1))
current_max = max(current_max, next_val)
return best
print(smallest_range([[4,10,15,24,26],[0,9,12,20],[5,18,22,30]]))
# [20, 24]Det k-te minste elementet i en sortert matrise
Det k-te minste elementet i en sortert matrise (LeetCode #378): en n×n-matrise der hver rad og kolonne er sortert. Finn det k-te minste elementet. Behandle hver rad som en sortert liste, og bruk k-veis fletting med en heap. Alternativt kan De bruke binærsøk i verdiområdet. Heaptilnærmingen har kompleksitet O(k log n), noe som er effektivt når k er lite; binærsøk har kompleksitet O(n log(max-min)) og fungerer bedre for store k.
import heapq
def kth_smallest_matrix(matrix, k):
n = len(matrix)
heap = [(matrix[0][0], 0, 0)]
count = 0
visited = {(0, 0)}
while heap:
val, r, c = heapq.heappop(heap)
count += 1
if count == k:
return val
# Push right neighbor
if c + 1 < n and (r, c+1) not in visited:
heapq.heappush(heap, (matrix[r][c+1], r, c+1))
visited.add((r, c+1))
# Push bottom neighbor
if r + 1 < n and (r+1, c) not in visited:
heapq.heappush(heap, (matrix[r+1][c], r+1, c))
visited.add((r+1, c))
return -1
matrix = [[1,5,9],[10,11,13],[12,13,15]]
print(kth_smallest_matrix(matrix, 8)) # 13To heap-er for løpende statistikk
Mønsteret med to heap-er generaliserer utover medianen. De kan bruke det til å vedlikeholde en løpende kvantil (for eksempel 25-persentilen): tilpass den nedre heapen slik at den inneholder p*n elementer, og den øvre heapen slik at den inneholder (1-p)*n elementer. Hver gang et element legges til, balanserer De som før. Dette mønsteret forekommer i problemer med strømmende statistikk, der De trenger effektiv innsetting og kvantilforespørsler samtidig.
import heapq
# Generalised two-heap for arbitrary quantile p
# lo contains floor(p * count) elements
# hi contains the remaining elements
class QuantileFinder:
def __init__(self, p):
self.p = p # quantile (e.g., 0.5 for median)
self.lo = [] # max-heap
self.hi = [] # min-heap
self.count = 0
def add(self, num):
self.count += 1
heapq.heappush(self.lo, -num)
heapq.heappush(self.hi, -heapq.heappop(self.lo))
# Target: lo should have floor(p * count) elements
target_lo = int(self.p * self.count)
while len(self.lo) < target_lo:
heapq.heappush(self.lo, -heapq.heappop(self.hi))
while len(self.lo) > target_lo:
heapq.heappush(self.hi, -heapq.heappop(self.lo))
def quantile(self):
return -self.lo[0] if self.lo else self.hi[0]
qf = QuantileFinder(0.5) # median
for n in [1, 2, 3, 4, 5, 6]: qf.add(n)
print(qf.quantile()) # 3 (median of 1-6)Finn k nærmeste punkter til origo
k nærmeste punkter til origo (LeetCode #973) bruker en maks-heap med størrelse k. Legg inn hvert punkts kvadrerte avstand (for å unngå kvadratrot). Når heapen blir større enn k, tar De ut det fjerneste punktet. De gjenværende k punktene er de k nærmeste. Dette har kompleksitet O(n log k). Et alternativ er quickselect med gjennomsnittlig O(n), men heapløsningen er enklere å implementere riktig og forklare i et intervju.
import heapq
def k_closest(points, k):
heap = [] # max-heap via negation
for x, y in points:
dist_sq = x*x + y*y
heapq.heappush(heap, (-dist_sq, x, y))
if len(heap) > k:
heapq.heappop(heap) # remove farthest
return [[x, y] for _, x, y in heap]
points = [[1,3], [-2,2], [5,8], [0,1], [-1,-1]]
print(k_closest(points, 2))
# Two closest to origin: [0,1] (dist=1) and [-1,-1] (dist=2)
# Verify by distances:
for x, y in points:
print(f'({x},{y}): dist^2 = {x*x+y*y}')Analyse av tids- og plasskompleksitet med to heap-er
Tilnærmingen med to heap-er for median gir O(log n) per addNum og O(1) per findMedian. Plassforbruket er O(n) for å lagre alle elementene. K-veis fletting bruker O(n log k) tid og O(k) plass for heapen. Dette er nær optimalt: De kan bevise en sammenligningsbasert nedre grense på Omega(n log k) for k-veis fletting, noe som viser at heapløsningen er asymptotisk optimal. Oppgi alltid disse kompleksitetene tydelig i intervjuer.
# Complexity summary for heap applications:
# Problem | Time per op | Space
# ----------------------|--------------|------
# MedianFinder.addNum | O(log n) | O(n)
# MedianFinder.find | O(1) | -
# Merge k sorted lists | O(n log k) | O(k)
# Kth smallest matrix | O(k log n) | O(n)
# K closest points | O(n log k) | O(k)
# Task scheduler | O(n log 26) | O(26)
# Kth largest stream | O(log k) | O(k)
# Sliding window median | O(n log k) | O(k)
print('Heap problems: identify k (heap size) vs n (input size)')Rask sjekk
Test forståelsen Deres av konseptene fra Data Structures & Algorithms — Coding Interview Prep i denne leksjonen.
Oppsummering av leksjonen
I denne leksjonen lærte De: to-heap-MedianFinder med innsetting på O(log n) og median på O(1), k-veis fletting med en min-heap på O(n log k) tid og O(k) plass, samt utvidelser som median for glidende vindu, minste intervall og k nærmeste punkter. Neste gang utforsker vi grafrepresentasjoner og oppsett for traversering.
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
Ofte stilte spørsmål
Er leksjonen «Median fra datastrøm og k-veis fletting» gratis?
Ja – hele teksten i «Median fra datastrøm og k-veis fletting» 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 «Median fra datastrøm og k-veis fletting»?
Vedlikehold to heaper, en max-heap for den minste halvdelen og en min-heap for den største, for medianoppdateringer i O(log n), og flett k sorterte lister med en heap. 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 «Median fra datastrøm og k-veis fletting»?
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
- Heap-egenskapen og arrayrepresentasjon
- Heapify, push og pop fra grunnen av
- Pythons heapq og triks for max-heap
- Median fra datastrøm og k-veis fletting