剑指Offer 41：数据流中的中位数
Leetcode 295. Find Median from Data Stream
- 首先使用python的堆库heapq，使用的方法如下
| Function |
Description |
| heappush(heap, x) |
将x压入堆中 |
| heappop(heap) |
从堆中弹出最小的元素 |
| heapify(heap) |
让列表具备堆特征 |
| heapreplace(heap, x) |
弹出最小的元素，并将x压入 |
| nlargest(n, iter) |
返回iter中n个最大的元素 |
| nsmallest(n, iter) |
返回iter中n个最小的元素 |
- heapq默认为最小堆，可以通过存入相反数转变为最大堆
方法一：构造最大堆+最小堆，其中最小堆和最大堆大小最多差一个，最小堆所有元素大于最大堆元素
class MedianFinder:
import heapq
def __init__(self):
"""
initialize your data structure here.
"""
self.min_heap, self.max_heap = list(), list()
def addNum(self, num: int) -> None:
if (len(self.min_heap) + len(self.max_heap)) % 2 == 0:
if len(self.min_heap) > 0 and num < -self.max_heap[0]:
heapq.heappush(self.min_heap, -heappop(self.max_heap))
heapq.heappush(self.max_heap, -num)
else:
heapq.heappush(self.min_heap, num)
else:
if num > self.min_heap[0]:
heapq.heappush(self.max_heap, -heappop(self.min_heap))
heapq.heappush(self.min_heap, num)
else:
heapq.heappush(self.max_heap, -num)
def findMedian(self) -> float:
if len(self.min_heap) + len(self.max_heap) == 0:
return None
elif (len(self.min_heap) + len(self.max_heap)) % 2:
return self.min_heap[0]
else:
return (self.min_heap[0] - self.max_heap[0]) / 2
Leetcode上的剪短写法
class MedianFinder:
import heapq
def __init__(self):
"""
initialize your data structure here.
"""
self.data = None, list(), list()
self.i = 1
def addNum(self, num: int) -> None:
heapq.heappush(self.data[self.i], -heapq.heappushpop(self.data[-self.i], num * self.i))
self.i *= -1
def findMedian(self) -> float:
return (-self.data[1][0] + self.i * self.data[-self.i][0]) / 2
