Median daripada Strim Data dan Gabungan K-Hala
Kekalkan dua heap (max-heap separuh kecil dan min-heap separuh besar) untuk kemas kini median O(log n), dan gabungkan k senarai tersusun menggunakan heap.
Median daripada Strim Data dan Gabungan K-Hala ialah pelajaran Persediaan Temu Duga Pengaturcaraan percuma di CoddyKit. Ini ialah pelajaran 4 daripada 4. Anda boleh membaca keseluruhan pelajaran di bawah secara percuma — kemudian berlatih secara praktikal dalam pelayar menggunakan penyunting kod terbina dalam dan tutor kecerdasan buatan 24/7. Pelajaran ini merupakan sebahagian daripada laluan pembelajaran Persediaan Temu Duga Pengaturcaraan, dan kemajuan anda disegerakkan merentas web serta aplikasi CoddyKit. Kursus Persediaan Temu Duga Pengaturcaraan merangkumi sejumlah 4 pelajaran.
Masalah Median daripada Strim Data
Cari Median daripada Strim Data (LeetCode #295) meminta anda menyokong dua operasi dengan cekap: addNum(num) untuk menambah nombor dan findMedian() untuk mengembalikan median semasa. Median bagi senarai yang panjangnya genap ialah purata dua nilai tengah. Senarai diisih secara naif memberikan penyisipan O(n) dan median O(1). Penyelesaian optimum menggunakan dua timbunan untuk penyisipan O(log n) dan median 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')Pelaksanaan MedianFinder dengan Dua Timbunan
Kekalkan timbunan maksimum untuk separuh bawah dan timbunan minimum untuk separuh atas. Sentiasa pastikan timbunan maksimum mempunyai saiz yang sama atau satu elemen lebih banyak daripada timbunan minimum. Apabila menambah nombor: lakukan push ke timbunan maksimum, kemudian seimbangkan dengan memindahkan nilai teratas timbunan maksimum ke timbunan minimum jika nilai itu melebihi minimum timbunan minimum, dan seimbangkan semula saiz jika perlu.
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.0Jejaki Langkah MedianFinder
Memahami sebab invarian dua timbunan dikekalkan adalah penting untuk menerangkan penyelesaian dalam temu duga. Mari kita jejaki penambahan [5, 15, 1, 3] langkah demi langkah. Selepas setiap penyisipan: seimbangkan supaya timbunan maksimum bahagian bawah menyimpan separuh nilai yang lebih kecil. Invarian tersebut memastikan max(lo) <= min(hi) sentiasa benar, lalu median boleh dicapai terus pada bahagian teratas salah satu atau kedua-dua timbunan.
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 Tetingkap Gelongsor
Median Tetingkap Gelongsor (LeetCode #480) ialah variasi yang lebih sukar: cari median bagi setiap tetingkap bersaiz k semasa tetingkap itu bergerak merentasi tatasusunan. Pendekatan dua timbunan diperluas dengan himpunan pemadaman tertunda untuk mengendalikan elemen yang keluar dari tetingkap. Apabila elemen meninggalkan tetingkap, tandakannya dalam himpunan pemadaman; apabila elemen itu sampai ke bahagian teratas mana-mana timbunan, buangkannya.
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]Penggabungan K Hala: Masalahnya
Gabungkan K Senarai Diisih (LeetCode #23) ialah masalah asas dengan aplikasi dalam pengisihan luaran, penggabungan pangkalan data dan sistem teragih. Diberikan k senarai terpaut yang diisih dan mempunyai jumlah n nod, gabungkan semuanya menjadi satu senarai diisih. Pendekatan naif (merge dua senarai pada satu-satu masa) mempunyai kerumitan O(kn) atau O(n log k) dengan pendekatan bahagi dan takluk. Pendekatan timbunan memproses setiap nod tepat sekali dengan kerja O(log k) bagi setiap nod: jumlahnya 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')Penggabungan K Hala dengan Timbunan Minimum
Mulakan timbunan dengan nod pertama bagi setiap senarai. Pada setiap langkah, lakukan pop pada minimum, tambahkannya pada hasil, dan lakukan push pada nod seterusnya daripada senarai itu, jika ada. Timbunan sentiasa mempunyai paling banyak k elemen — satu kepala bagi setiap senarai aktif. Oleh sebab kita memproses sejumlah n nod dengan operasi timbunan O(log k) bagi setiap nod, jumlah masa ialah O(n log k) dan ruang ialah O(k) untuk timbunan.
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]Julat Terkecil yang Meliputi K Senarai
Julat Terkecil (LeetCode #632) mencari julat terkecil [lo, hi] supaya sekurang-kurangnya satu elemen daripada setiap k senarai yang diisih berada dalam julat tersebut. Gunakan timbunan minimum yang dimulakan dengan elemen pertama setiap senarai dan jejaki maksimum semasa. Kecilkan julat dengan sentiasa bergerak ke elemen seterusnya dalam senarai yang mempunyai minimum semasa. Berhenti apabila mana-mana senarai kehabisan elemen.
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]Elemen Ke-k Terkecil dalam Matriks
Elemen Ke-k Terkecil dalam Matriks Diisih (LeetCode #378): sebuah matriks n×n yang setiap baris dan lajurnya telah diisih. Cari elemen ke-k terkecil. Anggap setiap baris sebagai senarai diisih dan gunakan penggabungan k hala dengan timbunan. Sebagai alternatif, gunakan carian binari pada julat nilai. Pendekatan timbunan mempunyai kerumitan O(k log n), yang cekap apabila k kecil; carian binari mempunyai kerumitan O(n log(max-min)), yang lebih sesuai untuk k besar.
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)) # 13Dua Timbunan untuk Statistik Berjalan
Corak dua timbunan boleh digeneralisasikan melangkaui median. Anda boleh menggunakannya untuk mengekalkan kuantil berjalan (contohnya, persentil ke-25): saizkan timbunan bawah supaya menyimpan p*n elemen dan timbunan atas supaya menyimpan (1-p)*n elemen. Setiap kali elemen ditambah, seimbangkan semula seperti sebelum ini. Corak ini muncul dalam masalah statistik penstriman yang memerlukan penyisipan cekap dan pertanyaan kuantil secara serentak.
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)Cari K Titik Terdekat dengan Asal
K Titik Terdekat dengan Asal (LeetCode #973) menggunakan timbunan maksimum bersaiz k. Lakukan push pada jarak kuasa dua bagi setiap titik untuk mengelakkan pengiraan punca kuasa dua. Apabila timbunan melebihi k, keluarkan titik yang paling jauh dengan pop. K titik yang tinggal ialah k titik yang paling dekat. Kerumitannya ialah O(n log k). Sebagai alternatif, gunakan algoritma pemilihan pantas dengan kerumitan purata O(n), tetapi penyelesaian menggunakan timbunan lebih mudah dilaksanakan dengan betul dan diterangkan semasa temu duga.
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}')Analisis Masa dan Ruang Dua Timbunan
Pendekatan dua timbunan untuk median mencapai O(log n) bagi setiap addNum dan O(1) bagi findMedian. Ruang ialah O(n) untuk menyimpan semua elemen. Penggabungan k hala mengambil masa O(n log k) dan ruang O(k) untuk timbunan. Ini hampir optimum: anda boleh membuktikan had bawah berasaskan perbandingan Omega(n log k) untuk penggabungan k hala, yang menunjukkan penyelesaian timbunan adalah optimum secara asimptotik. Sentiasa nyatakan kerumitan ini dengan jelas dalam temu duga.
# 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)')Semakan Pantas
Uji pemahaman anda tentang konsep Struktur Data & Algoritma — Persediaan Temu Duga Pengekodan daripada pelajaran ini.
Ringkasan Pelajaran
Dalam pelajaran ini anda mempelajari: MedianFinder dengan dua timbunan yang mencapai penyisipan O(log n) dan median O(1), penggabungan k hala dengan timbunan minimum dalam masa O(n log k) dan ruang O(k), serta peluasan termasuk median tetingkap gelongsor, julat terkecil dan titik k-terdekat. Seterusnya kita meneroka perwakilan graf dan persediaan rentasan.
Pelajari Persediaan Temu Duga Pengaturcaraan dengan tutor kecerdasan buatan — percuma
Tulis dan jalankan kod sebenar dalam pelayar anda, dapatkan bantuan segera daripada tutor kecerdasan buatan yang tersedia 24/7, dan sambung semula dari tempat anda berhenti di web atau dalam aplikasi.
- Kursus
- 90
- Pelajaran
- 360
Soalan Lazim
Adakah pelajaran “Median daripada Strim Data dan Gabungan K-Hala” percuma?
Ya — teks penuh “Median daripada Strim Data dan Gabungan K-Hala” boleh dibaca secara percuma di web ini. Untuk berlatih secara interaktif menggunakan penyunting kod terbina dalam dan tutor kecerdasan buatan 24/7, serta membuka kunci baki kursus Persediaan Temu Duga Pengaturcaraan, tingkat taraf kepada CoddyKit PRO. Kursus Persediaan Temu Duga Pengaturcaraan merangkumi sejumlah 4 pelajaran.
Apakah yang akan saya pelajari dalam “Median daripada Strim Data dan Gabungan K-Hala”?
Kekalkan dua heap (max-heap separuh kecil dan min-heap separuh besar) untuk kemas kini median O(log n), dan gabungkan k senarai tersusun menggunakan heap. Anda berlatih Persediaan Temu Duga Pengaturcaraan menggunakan kod praktikal yang dijalankan terus dalam pelayar, manakala tutor kecerdasan buatan 24/7 menjawab soalan anda semasa anda mengikuti pelajaran.
Adakah saya memerlukan pengalaman untuk memulakan Persediaan Temu Duga Pengaturcaraan?
Tiada pengalaman terdahulu diperlukan. Pembelajaran Persediaan Temu Duga Pengaturcaraan di CoddyKit disusun untuk pelajar daripada peringkat pemula hingga lanjutan, jadi anda boleh bermula di sini atau dari awal dan belajar mengikut kadar anda sendiri. Ini ialah pelajaran 4 daripada 4.
Berapa lamakah pelajaran “Median daripada Strim Data dan Gabungan K-Hala” diambil?
Kebanyakan pelajaran CoddyKit mengambil masa kira-kira 5–10 minit. Setiap pelajaran ringkas dan interaktif, jadi anda boleh membuat kemajuan secara berterusan dan menyambung tepat dari tempat anda berhenti di web atau aplikasi.
Bolehkah saya menulis dan menjalankan kod dalam pelajaran Persediaan Temu Duga Pengaturcaraan ini?
Ya. Setiap pelajaran Persediaan Temu Duga Pengaturcaraan menyertakan penyunting kod terbina dalam, jadi anda boleh menulis dan menjalankan kod sebenar terus dalam pelayar serta menerima maklum balas kecerdasan buatan serta-merta — tanpa memerlukan persediaan setempat.
Semua pelajaran dalam kursus ini
- Sifat Heap dan Perwakilan Tatasusunan
- Heapify, Push dan Pop dari Awal
- heapq Python dan Helah Max-Heap
- Median daripada Strim Data dan Gabungan K-Hala