题解 | #数据流中的中位数#
数据流中的中位数
http://www.nowcoder.com/practice/9be0172896bd43948f8a32fb954e1be1
# -*- coding:utf-8 -*-
class Solution:
def __init__(self):
self.heap_min = []
self.heap_max = []
def Insert(self, num):
# write code here
import heapq
if len(self.heap_min) > len(self.heap_max):
heapq.heappush(self.heap_max, num)
else:
heapq.heappush(self.heap_min, -num)
if len(self.heap_min)>0 and len(self.heap_max)>0 and -self.heap_min[0] > self.heap_max[0]:
retMin = -heapq.heappop(self.heap_min)
retMax = heapq.heappop(self.heap_max)
heapq.heappush(self.heap_min, -retMax)
heapq.heappush(self.heap_max, retMin)
def GetMedian(self):
# write code here
if len(self.heap_min) > len(self.heap_max):
return -self.heap_min[0]
else:
return (-self.heap_min[0]+self.heap_max[0])/2.0
class Solution:
def __init__(self):
self.heap_min = []
self.heap_max = []
def Insert(self, num):
# write code here
import heapq
if len(self.heap_min) > len(self.heap_max):
heapq.heappush(self.heap_max, num)
else:
heapq.heappush(self.heap_min, -num)
if len(self.heap_min)>0 and len(self.heap_max)>0 and -self.heap_min[0] > self.heap_max[0]:
retMin = -heapq.heappop(self.heap_min)
retMax = heapq.heappop(self.heap_max)
heapq.heappush(self.heap_min, -retMax)
heapq.heappush(self.heap_max, retMin)
def GetMedian(self):
# write code here
if len(self.heap_min) > len(self.heap_max):
return -self.heap_min[0]
else:
return (-self.heap_min[0]+self.heap_max[0])/2.0
