中位数是有序列表中间的数。如果列表长度是偶数,中位数则是中间两个数的平均值。
例如,
[2,3,4] 的中位数是 3
[2,3] 的中位数是 (2 + 3) / 2 = 2.5
设计一个支持以下两种操作的数据结构:
void addNum(int num) - 从数据流中添加一个整数到数据结构中。 double findMedian() - 返回目前所有元素的中位数。 示例:
addNum(1) addNum(2) findMedian() -> 1.5 addNum(3) findMedian() -> 2 进阶:
如果数据流中所有整数都在 0 到 100 范围内,你将如何优化你的算法? 如果数据流中 99% 的整数都在 0 到 100 范围内,你将如何优化你的算法?
需要明确的是:大顶堆中的元素是小顶堆里最小值取负后再加入的,因此大顶堆中(忽略负号)的元素肯定比小顶堆中的小。然后,让小顶堆的长度总是大于或等于大顶堆。因此当长度为奇数时,中位数就是小顶堆的堆首,为偶数时就是(大顶堆堆首+小顶堆堆首)/2
import heapq
class MedianFinder(object):
def __init__(self):
"""
initialize your data structure here.
"""
self.len = 0
#小顶堆
self.minheap = []
#大顶堆
self.maxheap = []
def addNum(self, num):
"""
:type num: int
:rtype: None
"""
#加入一个数,长度加1
self.len += 1
#首先明确的是python中的heapq是小顶堆
#heappushpop:将num放入堆中,然后弹出并返回heap的最小元素。
#heappush:将item的值加入heap中,保持堆的不变性。
#heappop:弹出并返回heap的最小的元素,保持堆的不变性。
heapq.heappush(self.maxheap, -heapq.heappushpop(self.minheap, num))
if len(self.maxheap) > len(self.minheap):
heapq.heappush(self.minheap, -heapq.heappop(self.maxheap))
print("小顶堆:",self.minheap)
print("大顶堆:",self.maxheap)
def findMedian(self):
"""
:rtype: float
"""
if self.len & 1 == 0:
return (self.minheap[0] - self.maxheap[0]) / 2.0
return self.minheap[0]
m=MedianFinder()
m.addNum(4)
print("中位数:",m.findMedian())
m.addNum(1)
print("中位数:",m.findMedian())
m.addNum(5)
print("中位数:",m.findMedian())
m.addNum(2)
print("中位数:",m.findMedian())
m.addNum(7)
print("中位数:",m.findMedian())
过程:负号只是占位用。