從資料流中尋找中值
「從資料流中尋找中位數」問題的詳細指南和 Python 實作。
1. 學習
「從資料流中尋找中值」問題是堆/優先權佇列部分的關鍵挑戰。
此實作重點在於 Python 中的硬級邏輯。
在我們提供的解決方案中，我們優先考慮技術準確性和程式碼可讀性。
2. Real-World Applications
3. Visual Intuition
可視化從資料流查找中值的邏輯流程。
4. Prerequisites
5. Step-by-Step Thinking
1. Understand the problem
仔細閱讀「從資料流中尋找中位數」的問題陳述。
2. Formulate brute force
起草一個簡單的迭代解決方案。
3. Identify inefficiency
尋找冗餘計算。
4. Optimize search path
使用散列或排序來加速該過程。
5. Final Implementation
清理生產標準代碼。
問題陳述
中位數是有序整數列表中的中間值。如果清單的大小是偶數，則沒有中間值，中位數是中間兩個值的平均值。
實作 MedianFinder 類別：
- MedianFinder() 初始化 MedianFinder 物件。
- addNum(num: int) 將資料流中的整數 num 加入資料結構。
- findMedian() -> float 傳回到目前為止所有元素的中位數。
輸入是操作和參數的清單。實作一個傳回結果清單的函數 medianFinder(operations: list, arguments: list) -> list （建構子/addNum 為 None，findMedian 為 float）。
- •-10^5 <= num <= 10^5
- •There will be at least one element in the data structure before calling findMedian
- •At most 5 * 10^4 calls will be made to addNum and findMedian
範例
operations = ["MedianFinder", "addNum", "addNum", "findMedian", "addNum", "findMedian"], arguments = [[], [1], [2], [], [3], []]
[None, None, None, 1.5, None, 2.0]
Initialize. Add 1, 2. Median is 1.5. Add 3. Median is 2.0.
Need a Hint?
Edge Cases to Watch
- 空輸入結構
- 單元素輸入
- 大數值範圍
準備好解決了嗎？
Open the problem in PyRun's browser-based Python editor. Your code runs fully offline — no server required.
面試見解和變化
複雜度分析分解
為什麼時間: Directly evaluates all possibilities.
為什麼選擇太空: Uses standard local memory.
為什麼時間: Optimized paths reduce total operations.
為什麼選擇太空: May trade memory for speed.
最佳化解決方案Python程式碼
最佳化解決方案Python程式碼
import heapq
class MedianFinderOpt:
def __init__(self):
self.small, self.large = [], []
def addNum(self, num):
heapq.heappush(self.small, -1 * num)
if self.small and self.large and (-1 * self.small[0]) > self.large[0]:
val = -1 * heapq.heappop(self.small)
heapq.heappush(self.large, val)
if len(self.small) > len(self.large) + 1:
val = -1 * heapq.heappop(self.small)
heapq.heappush(self.large, val)
if len(self.large) > len(self.small) + 1:
val = heapq.heappop(self.large)
heapq.heappush(self.small, -1 * val)
def findMedian(self):
if len(self.small) > len(self.large): return -1 * self.small[0]
if len(self.large) > len(self.small): return self.large[0]
return (-1 * self.small[0] + self.large[0]) / 2暴力破解代碼（劇透保護）
暴力破解代碼（劇透保護）
class MedianFinderBrute:
def __init__(self):
self.nums = []
def addNum(self, num):
self.nums.append(num)
def findMedian(self):
self.nums.sort()
n = len(self.nums)
if n % 2: return self.nums[n//2]
return (self.nums[n//2-1] + self.nums[n//2]) / 2Algorithm Pattern Checklist
When dealing with Heap / Priority Queue data patterns.
- Are constraints clear?
- Is there a linear or logarithmic optimization possible?
PyRun is built and maintained by an independent solo developer. If this helped your interview prep, consider buying a coffee!
推薦的 Python 資源
透過相關的互動式教學、備忘單和程式碼比較來擴展您的知識。
Python 迴圈：For 與 While 迴圈解釋
了解如何使用 Python 循環來迭代資料。透過互動式範例掌握 for 迴圈、while 迴圈、break、continue 和迴圈最佳實務。
如何在 Python 中刪除清單中的重複項
了解如何從 Python 清單中刪除重複項，同時保持或忽略順序。比較集合轉換、字典鍵和循環方法。
Python 集合和資料結構備忘單
Python 集合模組和本機資料結構的完整指南。學習清單、字典、集合、元組、雙端佇列和命名元組。
Python 與 JavaScript：哪種程式語言最好？
Python 和 JavaScript 的全面比較。探索語法差異、效能、用例（後端與前端）和編碼範例。